0-1 Knapsack Problem using Dynamic Programming

Let i be the highest-numbered item in an optimal solution S for W pounds. Then S' = S - {i} is an optimal solution for W - wi pounds and the value to the solution S is Vi plus the value of the subproblem.

We can express this fact in the following formula: define c[i, w] to be the solution for items 1,2, ..., i and maximum weight w. Then c[i,w] can be represented as:

0 if i = 0 or w = 0 c[i,w] = c[i-1, w] if wi >= 0 max [vi + c[i-1, w - wi], c[i - 1, w]} if i > 0 and w >= wi

This says that the value of the solution to i items either include ith item, in which case it is vi plus a subproblem solution for (i - 1) items and the weight excluding wi, or does not include ith item, in which case it is a subproblem's solution for (i - 1) items and the same weight. That is, if the thief picks item i, thief takes vi value, and thief can choose from items w - wi, and get c[i - 1, w - wi] additional value. On other hand, if thief decides not to take item i, thief can choose from item 1,2, ..., i-1 upto the weight limit w, and get c[i - 1, w] value. The better of these two choices should be made.

The algorithm takes the maximum weight W as input, the number of items n, and the two sequences v = < v1, v2, ..., vn > and w = < w1, w2, ..., wn >. It stores the c[i, j] values in the table, that is, a two dimensional array, c[0 .. n, 0 .. w] whose entries are computed in a row-major order. That is, the first row of c is filled in from left to right, then the second row, and so on. At the end of the computation, c[n, w] contains the maximum value that can be picked into the knapsack.

Algorithm: Dynamic-0-1-knapsack (v, w, n, W)

FOR w = 0 TO W DO c[0, w] = 0 FOR i=1 to n DO c[i, 0] = 0 FOR w=1 TO W DO IFf wi <= w THEN IF vi + c[i-1, w-wi] THEN c[i, w] = vi + c[i-1, w-wi] ELSE c[i, w] = c[i-1, w] ELSE c[i, w] = c[i-1, w]

The set of items to take can be deduced from the table, starting at c[n. w] and tracing backwards where the optimal values came from. If c[i, w] = c[i-1, w] item i is not part of the solution, and we are continue tracing with c[i-1, w]. Otherwise item i is part of the solution, and we continue tracing with c[i-1, w-W].

---

Analysis

---

This dynamic-0-1-kanpsack algorithm takes Big-Theta(nw) times, broken up as follows: Big-Theta(nw) times to fill the c-table, which has (n +1).(w +1) entries, each requiring Big-Theta(1) time to compute. O(n) time to trace the solution, because the tracing process starts in row n of the table and moves up 1 row at each step.

---

Happy Exploring!