Knapsack problems ask how to choose items under a limited capacity. Each item usually has a cost, weight, or size, and may also have a value.
Knapsack is a standard way to learn choice-based dynamic programming.
Core Idea
For each item, the algorithm decides whether to take it or skip it. The state must remember enough information to respect the capacity limit.
In 0/1 knapsack, each item can be used at most once.
Python Example
def knapsack(weights, values, capacity):
dp = [0] * (capacity + 1)
for weight, value in zip(weights, values):
for current in range(capacity, weight - 1, -1):
dp[current] = max(dp[current], dp[current - weight] + value)
return dp[capacity]The capacity loop goes backward so the same item is not reused in the same iteration.
Common Confusions
0/1 knapsack and unbounded knapsack use different loop directions. Reusing an item changes the recurrence.
The capacity value may make the DP table large even when the number of items is small.
When To Use It
Use knapsack reasoning when each choice consumes a limited resource and the algorithm must optimize value, count, or feasibility under that limit.