平衡石头

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实现。