DP Table = array[i][W]

Value Table = p[i]

Weight Table = w[i]

Total element = max_i

Restriction on Knapsack = max_w

Recursive Relationship (Sequential passing of element i):

\(S(i, W) = max \{S(i-1, W), p[i] + S(i-1, W-w[i]) \} \) (Starting at S(max_i, max_w) ) or

\(S(i, W) = max \{S(i+1, W), p[i] + S(i+1, W+w[i] \} \) (Starting at S(0,0) and limited by max_i & max_w)

Bottom-up (Incremental addition of element i):

Firstly, \(S(i,0) = 0\) and \(S(0,W)=0\) for all \(i,W\).

For i = 1 to max_i,

For W = 1 to max_w,

S(i,W) = max( S(i-1, W), S(i-1, W - w[i]) + p[i] ) (Direct translation of recursion!)