0-1 Knapsack revisited

Question

Well, this is an old 0-1 Knapsack problem but after finding the total maximum price I can get I need to find the the items I can carry. But for the following test case ( total 3 items)

10 (max weight that I can carry)
5 3 (weight and value for each item)
5 2
6 5

Here maximum price is 5. But for weight it can be 6 or 10(5+5) . Both will give the same price but obviously the feasible would be to take 6 kg item than 10 kg. I want hint how can I calculate this from the dp matrix. I got the following matrix for this test case.

0 0 0 0 3 3 3 3 3 3 
0 0 0 0 3 3 3 3 3 5 
0 0 0 0 3 5 5 5 5 5 

Using this algo it finds weight as 10 but the optimal is 6 kg.

i=n, k=W(max weight)// n= total items

while i,k > 0

if dp[i,k] ≠ dp[i−1,k] then 
mark the ith item as in the knapsack
i = i−1, k = k-w(weight of ith item)

else
i = i−1

Answer 1

Simple solution is to iteratively run the knapsack algorithm on varying bag sizes, and chose the smallest bag that still gives you the same value the original bag gave you.

This can be done using binary search on the weigths [0,W] - so you will run the knapsack algorithm total of O(logW) times, giving you total of O(nW*log(W)) solution that finds maximal value and minimal possible bag size.

Idea of how to imply the binary search:
Let the original bag be of size W, run knapsack(W,items), and get the value. Now check if knapsack(W/2,items) still returns value. If it does - search in range (0,W/2]. If it doesn't, search in range (W/2,W], until you find the smallest bag size that returns value.