Knapsack DP

Choose items under a weight limit to maximise value - 0/1 and unbounded versions, subset sum, and the one-array trick where loop direction is the whole difference.

45 minCF 1500–20006 interactive8 problems

The problem

You have n items, each with a weight w and a value v, and a bag that holds total weight W. Pick items to maximise total value without exceeding W. Each item can be taken once. This is the 0/1 knapsack (0 = leave it, 1 = take it).

Brute force tries all $2^n$ subsets. For $n = 40$ that is already far too slow, yet n = 100 and W = 10000 is an easy DP.

1 of 7