algorithm - 具有两个权重的背包算法

Question

我有以下问题:

Solve the knapsack 0-1 problem(not fractional) Assuming that every object have weight w1 or w2 (there only two weights). Capacity=W, the algorithm must run on O(nlogn).

我试过求解，贪心算法不行，动态规划算法是O(n*W)。

谁能给我提示。 谢谢。

Answer 1

您可以将元素分成两部分，一部分的权重为 w1，另一部分的权重为 w2。

现在您可以根据成本对上面的两个列表进行排序。

A1 : sorted by cost in descending order, elements that have weight as w1

A2 : sorted by cost in descending order, elements that have weight as w2

现在您可以创建两个数组的前缀和，我们称它们为 P1, P2。

例子:

数组:11、8、5、3、1

前缀和:11, 19, 24, 27, 28

获得前缀总和后，您可以遍历 P1 数组并尝试包含直到第 i 个索引的元素。 一旦我们包含了 i 的元素，我们就剩下了 W - (w1*i) 权重，然后我们可以尝试在 P2 中对这个权重进行二分搜索> 数组。

伪代码:

A : input array
create A1 : cost of elements having w1 weight
create A2 : cost of elements having w2 weight

sort(A1, descending)
sort(A2, descending)

for(i=0;i <= A1.size();i++){
      P1[i] = P1[i-1] + A1[i];
      P2[i] = P2[i-1] + A2[i];
}
int ans = 0;
for(i=1;i<=A1.size();i++){
      if(i * w1 <= W){
            int wLeft = W - i * w1;
            int ans = binarySearch(wLeft, P2) + p1[i];  
      }
}
ans => contains the answer

//-----------Binary search function
int binarySearch(int weight, P2[]){
      int start = 0, end = P2.size(), ans = 0;
      int mid = (start+end)/2;
      while(start <= end){
            if(mid * w2 <= weight){
                  start = mid + 1;
                  ans = max(ans, p2[mid]);
            }else{
                  end = mid - 1;
            }
      }
return ans
}

整体复杂度为O(n * log n)。

正如@j_random_hacker 所建议的，我们可以迭代第二个前缀数组，因为我们只能通过添加元素来改进解决方案，这将通过删除二进制搜索来简化代码。