a bit of dp: Notes on 0-1 Knapsack

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!)