平衡石头

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，因此如果不可能，您将需要不同的位集实现。