Printing Items that are in sack in knapsack
I have an iterative algorithm inspired by @NiklasB. that works when a recursive algorithm would hit some kind of recursion limit.
def reconstruct(i, w, kp_soln, weight_of_item):
"""
Reconstruct subset of items i with weights w. The two inputs
i and w are taken at the point of optimality in the knapsack soln
In this case I just assume that i is some number from a range
0,1,2,...n
"""
recon = set()
# assuming our kp soln converged, we stopped at the ith item, so
# start here and work our way backwards through all the items in
# the list of kp solns. If an item was deemed optimal by kp, then
# put it in our bag, otherwise skip it.
for j in range(0, i+1)[::-1]:
cur_val = kp_soln[j][w]
prev_val = kp_soln[j-1][w]
if cur_val > prev_val:
recon.add(j)
w = w - weight_of_item[j]
return recon
From your DP table we know f[i][w] = the maximum total value of a subset of items 1..i that has total weight less than or equal to w.
We can use the table itself to restore the optimal packing:
def reconstruct(i, w): # reconstruct subset of items 1..i with weight <= w
# and value f[i][w]
if i == 0:
# base case
return {}
if f[i][w] > f[i-1][w]:
# we have to take item i
return {i} UNION reconstruct(i-1, w - weight_of_item(i))
else:
# we don't need item i
return reconstruct(i-1, w)