Printing items in a bag in a backpack

Question

Suppose you are a thief and you have invaded a house. Inside you found the following items:

A vase weighs 3 pounds and costs $ 50.
A silver nugget weighs 6 pounds and costs $ 30.
A painting weighs 4 pounds and costs $ 40.
A mirror weighs 5 pounds and costs $ 10.

The solution to this problem with a 10 pound backpack is $ 90.

Table from dynamic programming: -

Now I want to know what items I put in my bag using this table, and then how to go back

Answer 1

From your DP table, we know f [i] [w] = the maximum total value of a subset of elements 1..i, which has a total weight less than or equal to w.

We can use the table to restore the optimal packaging:

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) 

Answer 2

Using a loop:

  for (int n = N, w = W; n > 0; n--) { if (sol[n][w] != 0) { selected[n] = 1; w = w - wt[n]; } else selected[n] = 0; } System.out.print("\nItems with weight "); for (int i = 1; i < N + 1; i++) if (selected[i] == 1) System.out.print(val[i] +" "); 

Answer 3

I have an iterative algorithm inspired by @NiklasB. this works when the recursive algorithm hits 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