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-w_{i }pounds and the value to the solution S is V_{i} 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
0 if i = 0 or w = 0 c[i,w] = c[i-1, w] if w_{i }≥ 0 max [v_{i }+ c[i-1, w-w_{i}], c[i-1, w]} if i>0 and w ≥ w_{i}
This says that the value of the solution to i items either include i^{th} item, in which case it is v_{i }plus a subproblem solution for (i-1) items and the weight excluding w_{i}, or does not include i^{th} 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 v_{i} value, and thief can choose from items w-w_{i}, and get c[i-1, w-w_{i}] 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.
Although the 0-1 knapsack problem, the above formula for c is similar to LCS formula: boundary values are 0, and other values are computed from the input and "earlier" values of c. So the 0-1 knapsack algorithm is like the LCS-length algorithm given in CLR-book for finding a longest common subsequence of two sequences.
The algorithm takes as input the maximum weight W, the number of items n, and the two sequences v = <v_{1}, v_{2}, . . . , v_{n}> and w = <w_{1}, w_{2,} . . . , w_{n}>. 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.
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 if w_{i }≤ w
then if v_{i} + c[i-1, w-w_{i}]
then c[i, w] = v_{i} + c[i-1, w-w_{i}]
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 θ(nw) times, broken up as follows:
θ(nw) times to fill the c-table, which has (n+1).(w+1) entries, each requiring θ(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.