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.

Answer 1

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.