AI Hints
Home›DSA in Python Tutorial›More Dynamic Programming
DSA in Python · Lesson 94 of 132

The Knapsack Problem

Best value that fits.

⏱ 2 min read▶ Video at 1:52:24🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

A hiker's bag can hold ten kilos. There are items of different weights and values, a tent, a camera, food, a book. Which items should she pack, to carry the most value without going over the limit? Each item is either packed, or left behind.

The Knapsack Problem
From the video: The Knapsack Problem
  • A bag that holds 10 kg
  • Items with weights and values
  • Pack or leave each one

Zero one knapsack

Best of W means the best value we can carry with capacity W. For each item, we go through the capacities from high to low. Packing the item gives its value, plus the best value for the space that's left. We keep whichever is bigger, packing or not. Going from high to low makes sure each item is used only once. Run it. The best load is worth ninety five. The tent, the camera, and the stove, exactly ten kilos.

knapsack.pypython
def knapsack(items, capacity):
    best = [0] * (capacity + 1)
    for name, weight, value in items:
        for w in range(capacity, weight - 1, -1):
            best[w] = max(best[w], best[w - weight] + value)
    return best[capacity]

items = [("tent", 5, 40), ("camera", 2, 30), ("food", 4, 20), ("book", 3, 10), ("stove", 3, 25)]
print("best value:", knapsack(items, 10))
Output
best value: 95

Where knapsack appears

Knapsack is everywhere, in disguise. Choosing projects within a budget. Filling a delivery van. Picking adverts to fit a time slot. Whenever you choose items under a limit, to maximise a total, think knapsack. It runs in O of the number of items times the capacity.

keyvalue
Budgetchoose projects
Vanfill by weight
Advertsfit a time slot
CostO(items × capacity)

Summary

Zero one knapsack decides, for each item, whether packing it beats leaving it, for every capacity. Next, a dynamic programming puzzle about a careful burglar.

Key takeaways
  • best[w]
  • Pack it or not
  • Loop capacity downwards
Next up: Practice: House Robber — no two neighbours