Lesson 7 of 16

Take It or Leave It: Knapsack

Maximize the total value in a bag without exceeding its weight limit. Items cannot be split, and each may be used once. This is 0/1 knapsack: exclude an item or include it.

What changes from the coin problem?

The coin lesson allowed unlimited copies of a denomination. Here, reusing an item is invalid. Define a state as the best value achievable with capacity w using only the first i items.

• Exclude it: Keep the answer for the first i-1 items at the same capacity.
• Include it: Use the first i-1 items at the remaining capacity and add the current item’s value.
• Choose the larger result. If the item does not fit, only exclusion is possible.

Reduce the table to one row

items = [(2, 5), (3, 7), (4, 9)]
capacity = 5
dp = [0] * (capacity + 1)
for weight, value in items:
    for space in range(capacity, weight - 1, -1):
        dp[space] = max(dp[space], dp[space - weight] + value)
print(dp[capacity])

Items are (weight, value) pairs. The result is 12, using weights 2 and 3. Update from larger capacities down to smaller ones so dp[space-weight] still excludes the current item.

If capacities increase instead, an item of weight 2 can first update capacity 2, then be reused when capacity 4 reads that newly updated result.

What does “efficient” mean here?

For n items and integer capacity W, time is O(nW) and space is O(W). Large W is expensive. Representing W in the input needs far fewer digits, so this is not a polynomial-time solution in the full encoded input length. It is pseudo-polynomial.

If items can be split, the fractional knapsack problem permits a greedy method ordered by value per unit weight. That is a different set of conditions from 0/1 knapsack.

Check your understanding

There is one item (2, 5) and capacity 4. If a program returns 10, which rule did it violate?