# Knapsack problem

The knapsack problem is a combinatorial optimization problem in which a set of items, each with a value and a size, must be packed into a container of limited capacity so that the total value of the chosen items is as large as possible without the total size exceeding the capacity<sup>[1](https://developers.google.com/optimization/pack/knapsack?hl=en)</sup>. In its most studied form, the 0-1 knapsack problem, each item must be taken entirely or not at all. The problem is NP-hard, yet it admits pseudo-polynomial dynamic programming algorithms and fully polynomial-time approximation schemes, which makes it a standard testbed for exact, approximate, and heuristic optimization methods<sup>[2](https://web.cs.unlv.edu/larmore/Courses/CSC477/knap.html)</sup><sup> • </sup><sup>[3](https://www.sciencedirect.com/science/article/pii/S0305054821003877)</sup>.

| Key fact | Detail |
|---|---|
| Definition | Choose a subset of items with given values and sizes that maximizes total value subject to a capacity constraint<sup>[1](https://developers.google.com/optimization/pack/knapsack?hl=en)</sup> |
| Complexity | NP-hard; the 0-1 decision version is NP-complete, with no known algorithm polynomial in the input length<sup>[2](https://web.cs.unlv.edu/larmore/Courses/CSC477/knap.html)</sup> |
| Exact pseudo-polynomial algorithm | Dynamic programming in \( O(nK) \) time for \( n \) items and knapsack size \( K \)<sup>[2](https://web.cs.unlv.edu/larmore/Courses/CSC477/knap.html)</sup> |
| Approximation | FPTAS runtimes improved from \( O(n + 1/\varepsilon) \) (Sahni, 1975) to \( \tilde{O}(n + (1/\varepsilon)^{12/5}) \) (Chan, 2018)<sup>[4](https://d-nb.info/1365338754/34)</sup><sup> • </sup><sup>[5](https://arxiv.org/abs/1904.09562)</sup> |
| History | Studied since Mathews (1896); the name is attributed by folklore to Tobias Dantzig, father of George Dantzig<sup>[3](https://www.sciencedirect.com/science/article/pii/S0305054821003877)</sup> |
| Cryptographic role | Basis of the Merkle-Hellman public-key cryptosystem (1978), broken by Shamir's polynomial-time attack in 1982<sup>[6](https://journals.plos.org/plosone/article?id=10.1371%2Fjournal.pone.0322726)</sup> |
| Modern application | Blockchain block building is a knapsack variant: block producers select fee-paying transactions under block size or gas limits<sup>[7](https://arxiv.org/abs/2403.19077)</sup> |

## Statement of the problem

In the 0-1 knapsack problem, a planner is given \( n \) items, each with a positive profit and a weight, and a knapsack of limited capacity. The objective is to select a subset of items whose total weight does not exceed the capacity and whose total profit is maximal<sup>[8](https://doi.org/10.1016%2Fj.cor.2022.105848)</sup>. Formally, with binary variables \( x_i \in \{0,1\} \), the problem is to maximize \( \sum_{i=1}^{n} p_i x_i \) subject to \( \sum_{i=1}^{n} w_i x_i \le W \). The multidimensional version imposes \( d \) such linear constraints, one per resource, with the same binary variables<sup>[9](https://or-tools.github.io/docs/pdoc/ortools/algorithms/python/knapsack_solver.html)</sup>.

The 0-1 restriction is what creates the difficulty. When items are perfectly divisible, a greedy strategy that packs items in decreasing order of value per unit size fills the knapsack optimally; this fractional version traces to George B. Dantzig's 1957 study of the linear programming relaxation of the problem<sup>[7](https://arxiv.org/abs/2403.19077)</sup><sup> • </sup><sup>[3](https://www.sciencedirect.com/science/article/pii/S0305054821003877)</sup>. With indivisible items, no comparably simple rule is optimal, and the problem becomes NP-hard<sup>[7](https://arxiv.org/abs/2403.19077)</sup>.

## Variants

The knapsack family is broad. A 2025 survey organized 32 distinct variants into three groups: simple single-objective problems, multiple, multidimensional, and quadratic problems, and bi-objective, multi-objective, and many-objective problems<sup>[10](https://www.sciencedirect.com/science/article/pii/S0925231225028073)</sup>. The basic variants covered by the classic monographs of Martello and Toth (1990) and Kellerer, Pferschy, and Pisinger (2004) include the binary problem, subset sum, bounded and unbounded knapsack, change-making, and multiple knapsack<sup>[3](https://www.sciencedirect.com/science/article/pii/S0305054821003877)</sup>.

**Subset sum** is the special case in which each item's profit equals its weight; the goal is to find a subset whose sizes sum exactly to the knapsack size<sup>[3](https://www.sciencedirect.com/science/article/pii/S0305054821003877)</sup><sup> • </sup><sup>[2](https://web.cs.unlv.edu/larmore/Courses/CSC477/knap.html)</sup>. In the **unbounded** variant, variables may take any nonnegative integer value, and the problem can be reduced to the 0-1 case up to logarithmic factors<sup>[4](https://d-nb.info/1365338754/34)</sup>. The **multidimensional** knapsack problem (MKP) constrains several resources simultaneously and arises in [combinatorial auctions](https://www.edgepedia.org/combinatorial-auction), capital budgeting, cutting stock and cargo loading, project selection, and computer systems design<sup>[11](https://web.mit.edu/~dbertsim/www/papers/Stochastic%20Networks/An%20Approximate%20Dynamic%20Programming%20Approach%20to%20Multi-dimensional%20Knapsack%20Problems.pdf)</sup>. Research continues to add variants: a 2022 paper introduced the 0-1 Time-Bomb Knapsack Problem, a stochastic version in which each item carries a probability of exploding and destroying the entire contents, with applications in logistics and cloud computing scheduling<sup>[8](https://doi.org/10.1016%2Fj.cor.2022.105848)</sup>.

## Algorithms

Current algorithms fall into four broad categories: exact algorithms, approximation algorithms, heuristics, and metaheuristics<sup>[10](https://www.sciencedirect.com/science/article/pii/S0925231225028073)</sup>.

**Dynamic programming.** The classical pseudo-polynomial algorithm defines subproblems \( S(m, t) \), asking whether some subset of the first \( m \) item sizes sums to \( t \), and fills an \( (n+1) \times (K+1) \) table in \( O(nK) \) time, where \( K \) is the knapsack size<sup>[2](https://web.cs.unlv.edu/larmore/Courses/CSC477/knap.html)</sup>. A dual formulation indexes by profit instead of weight: an \( n \times (n \cdot p_{\max}) \) table stores, for each achievable profit \( p \), the smallest subset size that reaches it<sup>[12](https://people.csail.mit.edu/ghaffari/AA19/AAscript.pdf)</sup>. Both runtimes are pseudo-polynomial, polynomial in the numeric values but exponential in their bit length, which is why the problem remains NP-complete despite these algorithms<sup>[2](https://web.cs.unlv.edu/larmore/Courses/CSC477/knap.html)</sup>.

**Branch and bound.** Branch-and-bound methods explore the binary decision tree while pruning branches whose upper bounds fall below the best solution found. For the multidimensional problem, OR-Tools ships a generic branch-and-bound solver that handles large item counts and several dimensions; its brute-force solver, which explores all possible states, is limited to 30 items and one dimension and is competitive mainly for instances with fewer than 15 items<sup>[9](https://or-tools.github.io/docs/pdoc/ortools/algorithms/python/knapsack_solver.html)</sup>. For the single-capacity 0-1 problem, the most widely used exact approach remains the Combo algorithm of Martello, Pisinger, and Toth (1999)<sup>[3](https://www.sciencedirect.com/science/article/pii/S0305054821003877)</sup>.

**Approximation schemes.** The 0-1 knapsack problem admits a fully polynomial-time approximation scheme (FPTAS), an algorithm that for any \( \varepsilon > 0 \) returns a solution within a factor \( 1 + \varepsilon \) of optimal in time polynomial in \( n \) and \( 1/\varepsilon \)<sup>[12](https://people.csail.mit.edu/ghaffari/AA19/AAscript.pdf)</sup>. The recorded progression of runtimes starts with Sahni's \( O(n + 1/\varepsilon) \) scheme in 1975, passes through Ibarra and Kim (1975) and Lawler (1979), and reaches Chan's 2018 bound of \( \tilde{O}(n + (1/\varepsilon)^{12/5}) \), where \( \tilde{O} \) hides polylogarithmic factors<sup>[4](https://d-nb.info/1365338754/34)</sup><sup> • </sup><sup>[5](https://arxiv.org/abs/1904.09562)</sup>. For the densest instances, where lattice methods do not apply, the best known general approach is the Schroeppel-Shamir algorithm, running in \( 2^{n/2} \) time with \( 2^{n/4} \) bits of memory, later improved by Howgrave-Graham and Joux in 2010<sup>[6](https://journals.plos.org/plosone/article?id=10.1371%2Fjournal.pone.0322726)</sup>.

**Heuristics and learning methods.** For high-dimensional, multi-constrained, or multi-objective instances where exact methods face combinatorial explosion, metaheuristics such as genetic algorithms and ant colony optimization are widely used<sup>[10](https://www.sciencedirect.com/science/article/pii/S0925231225028073)</sup>. [Approximate dynamic programming](https://www.edgepedia.org/approximate-dynamic-programming) for the multidimensional problem, using a heuristic that adaptively rounds the linear programming relaxation, produced high-quality solutions faster than the commercial solver CPLEX in the computational study of Bertsimas and Demir<sup>[11](https://web.mit.edu/~dbertsim/www/papers/Stochastic%20Networks/An%20Approximate%20Dynamic%20Programming%20Approach%20to%20Multi-dimensional%20Knapsack%20Problems.pdf)</sup>. [Reinforcement learning](https://www.edgepedia.org/reinforcement-learning), in which an agent learns a policy mapping the current capacity and item selection to the next selection decision, remains an active research direction<sup>[13](https://www.sciencedirect.com/org/science/article/pii/S1546221825005090)</sup>.

## Applications

The problem models any binary allocation of a scarce resource. Documented uses include capital budgeting, cargo loading, cutting stock, project selection, and combinatorial auctions<sup>[11](https://web.mit.edu/~dbertsim/www/papers/Stochastic%20Networks/An%20Approximate%20Dynamic%20Programming%20Approach%20to%20Multi-dimensional%20Knapsack%20Problems.pdf)</sup>. In blockchain systems, block building is itself a knapsack variant: a block has finite size, transactions vary in fee and size, and the producer selects a subset that maximizes fees under the block size limit (data in Bitcoin, gas in Ethereum). Because a transaction is either included whole or not at all, the block production exercise is a 0-1 knapsack problem, and knapsack auctions have been proposed as a way to alleviate the maximal extractable value (MEV) problem<sup>[7](https://arxiv.org/abs/2403.19077)</sup>.

## Cryptography

The knapsack problem's [NP-hardness](https://www.edgepedia.org/np-hardness) made it an early candidate for public-key cryptography. In 1978 [Ralph Merkle](https://www.edgepedia.org/ralph-merkle) and Martin Hellman proposed a cryptosystem whose security rested on the hardness of the knapsack problem; it used super-increasing sequences and modular multiplication to build a trapdoor that made decryption easy with the private key<sup>[6](https://journals.plos.org/plosone/article?id=10.1371%2Fjournal.pone.0322726)</sup>. [Adi Shamir](https://www.edgepedia.org/adi-shamir) announced a polynomial-time attack on the singly-iterated system in the spring of 1982, followed by a string of attacks on other knapsack cryptosystems culminating in Brickell's attack on the multiply-iterated version; these attacks exploited the fact that modular multiplication does not fully disguise the easy knapsack underlying the construction<sup>[14](https://www-users.cse.umn.edu/~odlyzko/doc/arch/knapsack.survey.pdf)</sup>. Lattice-based attacks on general low-density knapsacks, due to Lagarias and Odlyzko (1985) and later Coster, Joux, LaMacchia, Odlyzko, Schnorr, and Stern (1991), raised the applicable density limit from 0.6463 to 0.9408<sup>[6](https://journals.plos.org/plosone/article?id=10.1371%2Fjournal.pone.0322726)</sup>. Interest in knapsack ciphers persists in post-quantum cryptography research, since the knapsack problem's NP-completeness is thought to resist quantum attack<sup>[6](https://journals.plos.org/plosone/article?id=10.1371%2Fjournal.pone.0322726)</sup>.

## Research activity

The field remains active. A bibliometric analysis indexed in [Web of Science](https://www.edgepedia.org/web-of-science) identified 2,314 papers on the topic, of which 570 from 2014 to 2025 were selected for a recent systematic survey<sup>[10](https://www.sciencedirect.com/science/article/pii/S0925231225028073)</sup>. Decades of work have produced exact algorithms that solve instances with thousands of decision variables in a short amount of time<sup>[15](https://ideas.repec.org/a/eee/ejores/v301y2022i3p841-854.html)</sup>, and a 2022 survey of single-knapsack problems reported continued new results in exact algorithms, heuristics, and approximation schemes<sup>[3](https://www.sciencedirect.com/science/article/pii/S0305054821003877)</sup>.

## References

1. [The Knapsack Problem, Google OR-Tools documentation](https://developers.google.com/optimization/pack/knapsack?hl=en)
2. [CSC 477/677: A Pseudo-Polynomial Time Dynamic Programming Algorithm for the Knapsack Problem, University of Nevada Las Vegas](https://web.cs.unlv.edu/larmore/Courses/CSC477/knap.html)
3. [Cacchiani et al. (2022). Knapsack problems — An overview of recent advances. Part I: Single knapsack problems. Computers & Operations Research.](https://www.sciencedirect.com/science/article/pii/S0305054821003877)
4. [Jin and Wu (2018). Approximation Schemes for 0-1 Knapsack. SOSA 2018.](https://d-nb.info/1365338754/34)
5. [An Improved FPTAS for 0-1 Knapsack. arXiv:1904.09562.](https://arxiv.org/abs/1904.09562)
6. [Bi, Su, Peng, Wang (2025). A simple and efficient attack on the Merkle-Hellman knapsack cryptosystem. PLOS One.](https://journals.plos.org/plosone/article?id=10.1371%2Fjournal.pone.0322726)
7. [Mohan and Khezr (2024). Blockchains, MEV and the knapsack problem: a primer. arXiv:2403.19077.](https://arxiv.org/abs/2403.19077)
8. [Strazzieri, Iori, and Monaci (2022). Exact algorithms for the 0–1 Time-Bomb Knapsack Problem. Computers & Operations Research.](https://doi.org/10.1016%2Fj.cor.2022.105848)
9. [ortools.algorithms.python.knapsack_solver API documentation](https://or-tools.github.io/docs/pdoc/ortools/algorithms/python/knapsack_solver.html)
10. [Recent Advances in Knapsack Problem: A Comprehensive Review of Models, Algorithms, and Applications. Neurocomputing (2026).](https://www.sciencedirect.com/science/article/pii/S0925231225028073)
11. [Bertsimas and Demir (2002). An Approximate Dynamic Programming Approach to Multidimensional Knapsack Problems. Management Science.](https://web.mit.edu/~dbertsim/www/papers/Stochastic%20Networks/An%20Approximate%20Dynamic%20Programming%20Approach%20to%20Multi-dimensional%20Knapsack%20Problems.pdf)
12. [Chapter 2: Approximation Schemes, MIT 6.006 lecture notes](https://people.csail.mit.edu/ghaffari/AA19/AAscript.pdf)
13. [Reinforcement Learning for Solving the Knapsack Problem. ScienceDirect (2025).](https://www.sciencedirect.com/org/science/article/pii/S1546221825005090)
14. [Odlyzko. The Rise and Fall of Knapsack Cryptosystems.](https://www-users.cse.umn.edu/~odlyzko/doc/arch/knapsack.survey.pdf)
15. [Jooken, Leyman, and De Causmaecker (2022). A new class of hard problem instances for the 0–1 knapsack problem. European Journal of Operational Research.](https://ideas.repec.org/a/eee/ejores/v301y2022i3p841-854.html)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Combinatorics › Combinatorics overview and reference*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license