knapsack algorithm with two weights

Question

I have questions which is the following:

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

I tried to solve, the greedy algorithm doesn't work, the dynamic programming algorithm is O(n*W).

Can anyone give me hint. Thank you.

uSeemSurprised uSeemSurprised · Accepted Answer · 2016-07-03T10:34:03

You can divide the elements in 2 parts, one that have w1 as weight and the other that have w2 as weight.

Now you can sort the two lists above according to their costs.

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

Now you can create prefix sum of both the array lets call them P1, P2.

example :

Array : 11, 8, 5, 3, 1

Prefix sum : 11, 19, 24, 27, 28

Once you have the prefix sum, you can iterate over the P1 array and try to include elements upto the ith index. Once we include elements upto i, we have W - (w1*i) weight left we can then try to binary search this weight in the P2 array.

Pseudo code :

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
}

The overall complexity is O(n * log n).

As suggested by @j_random_hacker we can iterate over the second prefix array, as we can only improve the solution by adding elements, it would simplify the code by removing the binary search.

knapsack algorithm with two weights

2 Answers