0
Challenge · 66Dynamic Programming

Knapsack

DPused in ~80% of apps

Choose from a set of items under a limit, and get the best total. It is the most disguised pattern in this tier, because the items are rarely called items and the limit is rarely called a limit. Learn the shape and a whole family of questions collapses into one.

Core idea. Consider the items one at a time. For each capacity, ask whether including the current item beats leaving it out. The table has one row per item and one slot per capacity, and the rows can be rolled into a single array if you read it in the right direction.
Playground, this isn't a screenshot
one rolling row, one item at a time
best value at each capacity
0
0
0
1
0
2
0
3
0
4
0
5
0
6
items
1: weight 1, value 1
2: weight 3, value 4
3: weight 4, value 5
one row, one slot per capacity. Everything starts at zero value
step 1 of 15

The direction of the inner loop is the whole difference between using an item once and using it as often as you like.

↑ play a little first, then dig in