0/1 Knapsack Problem

Select items to maximize value under a capacity constraint.

Also called: Knapsack Problem · 0/1 Knapsack · 배낭 문제

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.

Claims & evidence

Every relationship is a claim with an evidence grade; applicable problem-to-problem relationships also carry an equivalence level. See the evidence policy.

A–X describes evidence reliability; E0–E4 describes mathematical similarity between problems. The two axes are independent.

Relationships from this entry 6

uses method
0/1 Knapsack Problem to Dynamic Programming
The 0/1 knapsack problem can be solved exactly by pseudo-polynomial dynamic programming.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialKnapsack Problems
  Citation details
  Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
direct benchmark
0/1 Knapsack Problem to OR-Library
OR-Library distributes standard test instances including the knapsack family.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: B — Survey / tutorial / communityOR-Library
  Citation details
  Beasley, J.E. (1990). OR-Library: distributing test problems by electronic mail. JORS 41(11):1069-1072. Hosts instances for knapsack, bin packing, cutting stock and more.
shares method with
0/1 Knapsack Problem to 1D Cutting Stock
In cutting-stock column generation the pricing subproblem appears as an (integer) knapsack problem, methodologically linking the two.
EvidenceA · Peer-reviewed / official
Equiv.E3 · structural analogy
Sources
- Source grade: A — Peer-reviewed / officialA Linear Programming Approach to the Cutting-Stock Problem
  Citation details
  Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
uses method
0/1 Knapsack Problem to Branch and Bound
Besides dynamic programming, the 0/1 knapsack problem is also solved exactly by branch and bound.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialKnapsack Problems
  Citation details
  Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
uses method
0/1 Knapsack Problem to Integer Linear Programming
The 0/1 knapsack problem is directly formulated as a 0/1 integer linear program with binary variables and a single capacity constraint.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialKnapsack Problems
  Citation details
  Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
open-source implementation
0/1 Knapsack Problem to Google OR-Tools
Google OR-Tools provides an open-source KnapsackSolver for the 0/1 knapsack problem.
EvidenceC · Vendor / case-reported
Sources
- Source grade: C — Vendor / case-reportedGoogle OR-Tools (Opens in a new tab)

Relationships from this entry
Relationship	Claim	Evidence	Equiv.	Sources
uses method 0/1 Knapsack Problem to Dynamic Programming	The 0/1 knapsack problem can be solved exactly by pseudo-polynomial dynamic programming.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialKnapsack Problems Citation details Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
direct benchmark 0/1 Knapsack Problem to OR-Library	OR-Library distributes standard test instances including the knapsack family.	B · Survey / tutorial / community	—	Source grade: B — Survey / tutorial / communityOR-Library Citation details Beasley, J.E. (1990). OR-Library: distributing test problems by electronic mail. JORS 41(11):1069-1072. Hosts instances for knapsack, bin packing, cutting stock and more.
shares method with 0/1 Knapsack Problem to 1D Cutting Stock	In cutting-stock column generation the pricing subproblem appears as an (integer) knapsack problem, methodologically linking the two.	A · Peer-reviewed / official	E3 · structural analogy	Source grade: A — Peer-reviewed / officialA Linear Programming Approach to the Cutting-Stock Problem Citation details Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
uses method 0/1 Knapsack Problem to Branch and Bound	Besides dynamic programming, the 0/1 knapsack problem is also solved exactly by branch and bound.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialKnapsack Problems Citation details Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
uses method 0/1 Knapsack Problem to Integer Linear Programming	The 0/1 knapsack problem is directly formulated as a 0/1 integer linear program with binary variables and a single capacity constraint.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialKnapsack Problems Citation details Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
open-source implementation 0/1 Knapsack Problem to Google OR-Tools	Google OR-Tools provides an open-source KnapsackSolver for the 0/1 knapsack problem.	C · Vendor / case-reported	—	Source grade: C — Vendor / case-reportedGoogle OR-Tools (Opens in a new tab)

Relationships to this entry 1

generalizes
2D Knapsack to 0/1 Knapsack Problem
2D knapsack is a two-dimensional generalization of the 1D 0/1 knapsack problem, extending item selection to geometric placement.
EvidenceB · Survey / tutorial / community
Equiv.E2 · shared methodology
Sources
- Source grade: A — Peer-reviewed / officialKnapsack Problems
  Citation details
  Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.

Relationships to this entry
Relationship	Claim	Evidence	Equiv.	Sources
generalizes 2D Knapsack to 0/1 Knapsack Problem	2D knapsack is a two-dimensional generalization of the 1D 0/1 knapsack problem, extending item selection to geometric placement.	B · Survey / tutorial / community	E2 · shared methodology	Source grade: A — Peer-reviewed / officialKnapsack Problems Citation details Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.