Question

Consider the integer knapsack problem. Give a recursive algorithm (call it Find-Optimal-Subset) that finds the optimal subset of items through post-processing, that is, after filling in the memorization table to find the maximum total value of the optimal subset of items. (The algorithm we studied in class finds only the maximum total value, not the actual optimal subset of items.) Hint: Trace back through the array M[0..n,0..W] following the optimal structure.

Answer 1

The dynamic programming algorithm for kanapsack is given below:

knapsack(v, x, n, y)

FOR x = 0 TO y
DO c[0, x] = 0
FOR i=1 to n
DO c[i, 0] = 0
FOR x=1 TO y
DO IF xi ≤ x
THEN IF vi + c[i-1, x-xi]
THEN c[i, x] = vi + c[i-1, x-xi]
ELSE c[i, x] = c[i-1, x]
ELSE
c[i, x] = c[i-1, x]

We can see that from the table items to take can be deduced, starting at c[n. x] and where the optimal value came from tracing backward to that.
If c[i, x] = c[i-1, x] item i is not part of the solution, and the tracing will be continue with c[i-1, x]. Otherwise item i is part of the solution, and tracing will be continue with c[i-1, x-y].

θ(nx) time is taken by the dynamic knapsack algorithm, and the space taken is θ(nx) times to fill the table, which has (n +1).(x +1) entries in it, each of them required θ(1) computation times. To trace the solution O(n) times is required, it's only because the process of tracing starts in row n of the table and will be moving up 1 row at a time. (at every step).