पत्थरों को संतुलित करना

Question

आपके पास ज्ञात वजन w1, ..., wn के साथ कई पत्थरों हैं। एक कार्यक्रम लिखें जो पत्थरों को दो ढेर में पुनर्व्यवस्थित करेगा जैसे कि दो ढेर के बीच वजन अंतर न्यूनतम था। मैं डी पी एल्गोरिथ्म है:

int max(int a, int b){ 
    return a >= b ? a : b; 
} 

int diff(int* weights, int number_elements, int capacity){ 
    int **ptrarray = new int* [capacity + 1]; 

    for (int count = 0; count <= capacity; count++) { 
     ptrarray[count] = new int [number_elements + 1]; 
    } 

    for (int i = 0; i <= number_elements; ++i){ 
     ptrarray[0][i] = 0; 
    } 

    for (int i = 0; i <= capacity; ++i){ 
     ptrarray[i][0] = 0; 
    } 

    for (int i = 1; i <= number_elements; ++i){ 
     for (int j = 1; j <= capacity; ++j){ 
      if(weights[i - 1] <= j){ 
       ptrarray[j][i] = max(ptrarray[j][i - 1], ptrarray[j - weights[i - 1]][i-1] + weights[i - 1]); 
      } else{ 
       ptrarray[j][i] = ptrarray[j][i - 1]; 
      } 
     } 
    } 

    return ptrarray[capacity][number_elements]; 

} 




int main(){ 
    int capacity; 
    int number_elements; 

    cin >> number_elements; 

    int* weights = new int[number_elements]; 
    int sum = 0; 
    int first_half; 

    for (int i = 0; i < number_elements; ++i){ 
     cin >> weights[i]; 
     sum+=weights[i]; 
    } 

    first_half = sum/2; 
    int after; 

    after = diff(weights, number_elements, first_half); 
    cout << sum - 2*after; 
    return 0; 
} 

लेकिन यह एक छोटा सा अनुभवहीन है। यह बहुत अधिक स्मृति की मांग करता है, और मुझे इसे सरल बनाने के लिए कुछ संकेतों की आवश्यकता है। क्या एक और अधिक प्रभावी दृष्टिकोण है?

Answer 1

आप निम्न टिप्पणियों बनाकर स्मृति उपयोग को कम कर सकते हैं:

1. आपका कोड किसी भी समय ptrarray सरणी के केवल ज्यादा से ज्यादा दो परतों का उपयोग करता है।

2. यदि आप प्रत्येक परत में सबसे छोटी से छोटी अनुक्रमणिका में पुनरावृत्त करते हैं, तो आप पिछली परत को फिर से लिख सकते हैं। इस तरह आपको केवल एक सरणी की आवश्यकता होगी।

   max_weight = new int[max_capacity + 1](false) 
   max_weight[0] = true 
   for weight in weights: 
       for capacity in [max_capacity ... weight]: 
         max_weight[capacity] = max(max_weight[capacity], max_weight[capacity - weight] + weight 
   

   यह O(max_capacity) स्मृति (O(max_capacity * number_of_items) के बजाय) की आवश्यकता है:

यहाँ इस अनुकूलन के साथ एक छद्म कोड है।

कुछ और अनुकूलन: आप एक बुलियन सरणी का उपयोग कर सकते हैं (यह इंगित करने के लिए कि योग i पहुंच योग्य है या नहीं) और i से कम या उसके बराबर सबसे बड़ी राशि संग्रहीत करने के बजाय अंत में सबसे बड़ी पहुंच योग्य राशि चुनें। इसके अलावा, आप O(max_capacity * num_items/world_len) समय जटिलता प्राप्त करने के लिए बूलियन सरणी के बजाय std::bitset का उपयोग कर सकते हैं (जहां world_len सबसे बड़ा पूर्णांक प्रकार का आकार है जो मशीन लॉजिकल ऑपरेशंस कर सकता है)। एक वजन जोड़ना reachable |= (reachable << weight) जैसा दिखता है।

तो अंतिम संस्करण इस तरह दिखता है:

reachable = bitset(max_capacity + 1) 
reachable[0] = true 
for weight in weights: 
    reachable |= reachable << weight 
return highest set bit of reachable 

कोड बहुत सरल और अधिक कुशल इस तरह से हो जाता है (समय जटिलता तकनीकी रूप से एक ही है, लेकिन यह बहुत तेजी से व्यवहार में है)।

यहां एक चेतावनी है: आपको संकलन समय पर std::bitset के आकार को जानने की आवश्यकता है, इसलिए यदि यह संभव नहीं है, तो आपको एक अलग बिटसेट कार्यान्वयन की आवश्यकता होगी।