Take it or leave it

You are packing for a trip with a bag that holds 10 kg. Each item has a weight and a value. Which items give the most value?

Greedy fails here, and it is worth seeing why. Taking the most valuable first can fill the bag with one heavy item; taking the best value-per-kilogram first fails on items = [(6kg, 30), (5kg, 25), (5kg, 25)] with a 10 kg bag, because it takes the 6 kg item and then nothing else fits, for 30, while the two 5 kg items give 50.

The state needs two numbers

Where you are is no longer enough. You also need to know how much room is left:

best[i][w] = the most value using the first i items, with capacity w

And again, exactly two choices:

best[i][w] = max(
    best[i - 1][w],                                   # leave item i
    value[i] + best[i - 1][w - weight[i]]             # take item i
)

The second line only applies when weight[i] <= w.

Why this is the shape to learn properly

An enormous number of problems are this one wearing different clothes:

• Subset sum: can any subset total exactly T? Same table, storing true or false instead of a value.
• Partition into two equal halves: subset sum with T equal to half the total.
• Coin change: same structure, with unlimited copies of each coin.
• Counting subsets: same table, adding counts instead of taking a maximum.

Learning the table once and recognising it four more times is the return on this page.

Cost

O(n x W) time and memory, where W is the capacity. Note that this is not polynomial in the size of the input, because W is a number written in a few digits. A capacity of one billion makes this table impossible, and that is the tell that a problem wants something else.