平衡石頭

Question

你有許多石頭已知重量w1，...，wn。編寫一個程序，將石塊重新排列成兩堆，這樣兩堆之間的重量差異很小。 我有DP算法：

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的最大總和。此外，您可以使用std::bitset而不是布爾數組來獲得O(max_capacity * num_items/world_len)時間複雜度（其中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的大小，所以如果不可能的話，你需要一個不同的bitset實現。