Live briefing
Everything about Knapsack problem
Problem in combinatorial optimization
The knapsack problem is the following problem in combinatorial optimization:Given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Knapsack problemA 5-minute orientation
- Skim a recent paper: A new class of hard problem instances for the 0–1 knapsack problemInfluential work since 2022
- Pick up a classic book: Interfaces between computer science and operations researchThe most-reprinted book on the subject
- Read the landmark paper: The Multiple-Choice Knapsack ProblemCited 274 times
- Go sideways: Multiple subset sumA closely related topic
- Go sideways: Quadratic knapsack problemA closely related topic
📖 Definitions
Noun A problem in combinatorial optimization: given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
The Multiple-Choice Knapsack Problem
The stochastic knapsack problem
The quadratic knapsack problem—a survey
The knapsack problem: A survey
The Dynamic and Stochastic Knapsack Problem
The Knapsack Problem with Conflict Graphs
Unbounded knapsack problem: Dynamic programming revisited
A nonlinear Knapsack problem
🆕 Influential since 2022
A new class of hard problem instances for the 0–1 knapsack problem
The Online Knapsack Problem with Departures
The Knapsack Problem with forfeit sets
Matheuristic fixed set search applied to the multidimensional knapsack problem and the knapsack problem with forfeit sets
Nature-inspired algorithms for 0-1 knapsack problem: A survey
📚 Books worth reading
- 📕Interfaces between computer science and operations researchSymposium on Interfaces between Computer Science and Operations Research Amsterdam 1976. · 1978
Knapsack problemsHans Kellerer, Ulrich Pferschy · 2004
Knapsack problemsSilvano Martello · 1990
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Multiple subset sum The multiple subset sum problem is an optimization problem in computer science and operations research. It is a generalization of the subset sum problem…
- Quadratic knapsack problem The quadratic knapsack problem (QKP), first introduced in 19th century, is an extension of knapsack problem that allows for quadratic terms in the objective…
- Subset sum problem The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset S of integers and a target-sum…
- List of knapsack problems The knapsack problem is one of the most studied problems in combinatorial optimization, with many real-life applications. For this reason, many special…
- Continuous knapsack problem In theoretical computer science, the continuous knapsack problem (also known as the fractional knapsack problem) is an algorithmic problem in combinatorial…
- Fully polynomial-time approximation scheme A fully polynomial-time approximation scheme (FPTAS) is an algorithm for finding approximate solutions to function problems, especially optimization problems…
- Combinatorial optimization Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the…
- Pseudo-polynomial time In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is bounded from above by a polynomial function…