Build a table of best values: K[i,c] uses only the first i items and capacity c. Each new item is either skipped (keep the value above) or taken (its value plus the best for the capacity left over). The answer sits in the bottom-right corner, and a walk back up the table names the items.
- Average time
- O(nW)
- Space
- O(nW)