0/1 Knapsack Problem

Definition

Given items each with weight $w_i$ and value $v_i$, choose $x_i \in \{0,1\}$ to maximize $\sum v_i x_i$ subject to $\sum w_i x_i \le C$.

Example

Suppose a knapsack of capacity $C = 10$ and four items:

Item	Weight $w_i$	Value $v_i$
1	5	10
2	4	7
3	6	9
4	3	4

Among the subsets whose weights sum to at most 10, the highest total value is item set $\{1, 2\}$: weight $5 + 4 = 9 \le 10$, value $10 + 7 = 17$. Notably, item set $\{2, 3\}$ fills the capacity exactly at weight $4 + 6 = 10$ yet reaches only value $16$ — packing more weight does not make the solution better.

Why it's here

The knapsack problem connects to cutting & packing in two ways: (1) a shared method — dynamic programming, and (2) the pricing subproblem of 1D Cutting Stock's column generation is itself a knapsack problem.