Printing Items that are in sack in knapsack

Question

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 ??

score 12 · Accepted Answer · edited Dec 17 '20 at 06:23

12

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)

edited Dec 17 '20 at 06:23

mic

1,190
1
17
29

answered Apr 20 '14 at 19:01

Niklas B.

92,950
18
194
224

hey can u give me some inner idea to get more feeling about the this algo . – T.J. Apr 21 '14 at 03:00
@T.J You would need to be more specific about what you want to have explained better. The recursion works like this: if `f[i][w] <= f[i-1][w]`, then we don't need item i, so we just recurse into the subset `1..i-1`. If `f[i][w] > f[i-1][w]`, then we need to use item i to achieve an optimum result, so we pack it in the bag. The remaining bag has capacity `w-weight of item i`, and we want to pack as much as possible of items `1..i-1` into that remaining capacity – Niklas B. Apr 21 '14 at 05:41
I think the idea can be also stated as follows. At the end of the dynamic programming, an optimal state is selected to get the optimal value. The backtracking is used to find out which is the 'previous' state, i.e. the state based on which the optimal state was generated. The backtracking is then iterated on this previous state, until the initial state (i.e. the empty knapsack) is found. I find this quite insightful as I used to believe for several years that it is necessary to maintain some auxiliary structure to refer to the respective previous state during generation of the state space. – Codor May 10 '17 at 07:24
1

@Codor well, it *is* the case that additional information needs to be stored. To get the optimal value alone you would only ever need two consecutive lines of the DP array. – Niklas B. May 10 '17 at 10:16
@NiklasB. Very good point; for calculation the optimal value alone, not the entire state space needs to be represented at the same time. – Codor May 10 '17 at 10:32

score 1 · Answer 2 · answered Mar 03 '18 at 23:33

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

score 0 · Answer 3 · answered May 10 '17 at 06:50

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] +" ");

Printing Items that are in sack in knapsack

3 Answers3

Linked