algorithmdynamic-programmingknapsack-problem

Printing Items that are in sack in knapsack


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

A vase that weights 3 pounds and is worth 50 dollars.
A silver nugget that weights 6 pounds and is worth 30 dollars.
A painting that weights 4 pounds and is worth 40 dollars.
A mirror that weights 5 pounds and is worth 10 dollars.

Solution to this Knapsack problem of size 10 pounds is 90 dollars .

Table made from dynamic programming is :-

enter image description here

Now i want to know which elements i put in my sack using this table then how to back track ??


Solution

  • 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)