c++ - 平衡石头

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) )。

更多的优化:你可以使用一个 bool 数组(表示总和 i 是否可达)并在最后选择最大的可达总和而不是存储小于或等于 i 的最大总和。 .此外，您可以使用 std::bitset而不是 bool 数组来获得 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 的大小在编译时，所以如果不可能，您将需要不同的位集实现。