Consider the knapsack problem. (Problem definition: given n items of nonnegative
ID: 3807526 • Letter: C
Question
Consider the knapsack problem. (Problem definition: given n items of nonnegative weights w_i and nonnegative values v_i, and given a maximum capacity W, find a subset of the items that maximizes the total value (sigma_i v_i) subject to the max capacity limit (i.e., sigma_i w_i lessthanorequalto W).) Build on optimal substructure for this problem and write the resulting algorithm as a bottom-up (i.e., iterative) memorized program. Explain your optimal substructure. It suffices for the algorithm to find only the maximum total value and not the corresponding optimal subset of items.Explanation / Answer
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).