How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]?
Getting the elements you packed from the matrix can be done using the data from the matrix without storing any additional data.
Pseudo code:
line <- W
i <- n
while (i > 0):
if dp[line][i] - dp[line - weight(i)][i-1] == value(i):
// the element 'i' is in the knapsack
i <- i-1 // only in 0-1 knapsack
line <- line - weight(i)
else:
i <- i-1
The idea behind it is that you iterate the matrix; if the weight difference is exactly the element's size, it is in the knapsack. If it is not, the item is not in the knapsack, go on without it.
line <- W
i <- n
while (i> 0):
if dp[line][i] - dp[line - weight(i) ][i-1] == value(i):
the element 'i' is in the knapsack
cw = cw - weight(i)
i <- i-1
else if dp[line][i] > dp[line][i-1]:
line <- line - 1
else:
i <- i-1
Just remember how you got to dp[line][i] when you added item i
dp[line][i] = dp[line - weight(i) ][i - 1] + value(i);