The Knapsack Problem

Whole items only

An interactive lesson with 6 steps, about 5 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• In the knapsack problem, items are all-or-nothing.
• Greedy (best value per kilogram first) is fast but can miss the optimum.
• Exact knapsack is NP-hard in general, though practical methods work well.

Steps

1. Take it or leave it
2. Pack the rucksack
3. The greedy trap
4. Checking everything
5. Cutting the cheese
6. How hard?