The knapsack problem — optimisation

What just happened?

We have three items — A (weight 3, value 5), B (weight 2, value 3) and C (weight 2, value 3) — and a knapsack of capacity $W=4$. The greedy strategy reaches for the most valuable item A (value 5), but it takes up 3 of the 4 weight units and there is no room left for anything else. Meanwhile giving up A in favour of two cheaper items B + C gives value 6 with the knapsack exactly full (weight 4).

The knapsack problem — what is it?

It is a classic problem of combinatorial optimisation: given items of weights $w_i$ and values $v_i$ and a knapsack of capacity $W$, we pick a subset of maximum total value that fits inside it:

The constraint $\sum_i w_i \le W$ is hard — the total weight of the chosen items can never exceed the capacity. It is tempting to solve the task “greedily” (always take the most valuable item, or the locally best one with the largest ratio $v_i/w_i$), but — as seen above — this strategy does not guarantee the optimum.

Why is it hard? The class NP and “P vs NP”

Finding a guaranteed optimal solution requires considering many combinations of items, and the number of all subsets $2^n$ grows exponentially with the number of items: for 3 items that is 8 subsets, for 20 already over a million, for 50 — more than the number of atoms in many galaxies. That is why the knapsack problem belongs to the class of NP-hard problems, closely tied to one of the most important unsolved questions in mathematics and computer science: “P versus NP”. It is one of the 7 Millennium Prize Problems of the Clay Mathematics Institute (2000), and a prize of USD 1 million awaits its solution.

Where will you meet this in practice?

The knapsack problem has huge applications: packing cargo of limited mass, investment budgeting (which projects to fund within a fixed budget?), resource allocation, even cryptography. It shows that a seemingly simple task — “what to pack to carry away the most value?” — can be computationally very hard.

Why this matters for your exams:

It is a model example that the greedy strategy is not always optimal — the intuition “take the best now” can be misleading. The same caution helps in problems on optimisation, combinatorics and probability: before you declare the locally best move globally best, check for a counterexample.

Remember: in the knapsack problem the sum of the weights of the chosen items must satisfy $\sum_i w_i \le W$, and the goal is $\max \sum_i v_i$ — yet the greedy strategy does not guarantee the maximum value. Only an exhaustive search of the combinations gives a guarantee, and its cost grows exponentially. That is why the knapsack problem is NP-hard, and the question “P versus NP” still awaits an answer.