Subset Sum

Input Positive integers $w_1, w_2, ..., w_n$ and an integer $W$

Output A subset of the integers whose sum is as large as possible, but less than $W$

[ADD DESCRIPTION OF SUBPROBLEMS]

$$ M[j, c] = \begin{cases} 0 & \text{if } w_j = 0 \text{ or } c = 0\\ M[j-1, c] & \text{if } w_j > c\\ \max(M[j-1, c], w_j + M[j-1, c-w_j]) & \text{if } w_j \leq c \end{cases} $$

Then

for j from 1 to n:
    for c from 0 to W:
        calculate M[j,c]
return M[n, W]

Complexity

$O(nW)$ time as seen above.