0/1 Knapsack
Hard · Algorithms
You have a bag that holds at most capacity weight, and items that each have a weight and a value. Each item can be taken once or not at all (that is the "0/1"). Which items give the highest total value?
Dynamic programming: let best[w] be the highest value that fits in weight w. For each item, update best[w] = max(best[w], best[w - weight] + value), going from capacity DOWN to weight. Going downward makes sure each item is used at most once.
Write knapsack(weights, values, capacity) that returns the maximum total value. weights[i] and values[i] belong to item i. All numbers are non-negative integers, capacity <= 1000.