1

I'm solving a reverse 0/1 knapsack problem, i.e. I'm trying to recreate the list of weights and values of all the items using only the DP-table.

I have this table:

    [0][1]   [4][5][6]               [12]
[0]  0  0 0 0 0  0  0  0  0  0  0  0  0
[1]  0  4 4 4 4  4  4  4  4  4  4  4  4  
[2]  0  4 4 4 6 10 10 10 10 10 10 10 10

I don't understand how row [2] is possible.

[0] - it is clear that if we do not put anything in the knapsack, the answer total value 0.

[1] - in row [1] I see that [1][1]=4 and I hope that I correctly conclude that the first item has weight = 1 and value = 4. So, since we put only 1 item it is the only weight we can hope for in this row.

[2] - when we reach [2][4], we have 6, 6 > [2-1][4] and I assume that we use 2 items here, one weight = 1 and value = 4 (the old one) and weight = 4-1 and value = 6-4 = weight = 3 and value = 2, which is the new one.

Question: How is it possible to have [2][5] = 10? We can't put more than 1 item on a row, as I understand this chart. If we have two items in use here, shouldn't we have 6 for all the elements in row [2] starting from [2][4] to the end of the row?

ggorlen
  • 44,755
  • 7
  • 76
  • 106
alekscooper
  • 795
  • 1
  • 7
  • 19

1 Answers1

1

This seems possible if you have two items, one with weight 1 and value 4 and one with weight 4, value 6.

How? When you're at index (2, 4) you have a weight capacity of 4 for the first time in the row that considers item 2 (weight 4, value 6). This lets you take the item with value 6 instead of the weight 1, value 4 item you previously took at index (2, 3), effectively building from the subproblem at index (2, 0).

Now, when you're at index (2, 5) with a weight capacity of 5, the total value of 10 is possible because you can take both items. That's the best you can do for the rest of the row.

See also How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]?

ggorlen
  • 44,755
  • 7
  • 76
  • 106