0/1 Knapsack

A bag holds at most W kg. Item i weighs wt[i] kg and is worth val[i]. Take each item at most once. Return the most value that fits.

Examples

Example 1

Input:  wt = [1, 2, 4, 5], val = [5, 4, 8, 6], W = 5
Output: 13

Items 0 and 2: weight 1 + 4 = 5, value 5 + 8 = 13.