Knapsack Problem
A classic optimization problem for selecting items with weights and values to maximize value under a capacity limit
The Knapsack Problem is a classic optimization problem in which a set of items, each with a weight and a value, must be selected to maximize total value without exceeding a fixed weight capacity.
Definition
The Knapsack Problem is a classic optimization problem in which a set of items, each with a weight and a value, must be selected to maximize total value without exceeding a fixed weight capacity.
Overview
The knapsack problem gets its name from the intuitive scenario of a hiker packing a bag with limited capacity, choosing among items of varying weight and usefulness to maximize the total value carried. Despite its simple framing, it's a foundational problem in combinatorial optimization because it illustrates the difference between problems that are efficiently solvable and those that are not, depending on subtle variations in how the problem is defined. The most commonly taught variant, 0/1 knapsack, requires each item to be either fully included or excluded — no partial items and no duplicates. It's solved with dynamic programming using a table indexed by item count and remaining capacity, where each cell represents the best achievable value considering a subset of items up to a given weight limit; this gives a pseudo-polynomial time complexity of O(n·W), where n is the number of items and W is the capacity. The word "pseudo-polynomial" is important: the running time is polynomial in the numeric value of W, not in the number of bits needed to represent W, and 0/1 knapsack is in fact NP-complete in the general sense, meaning no known algorithm solves it in time truly polynomial in the input's bit-length for arbitrarily large capacities. Several variants extend the base problem: fractional knapsack allows taking partial amounts of an item and is solved optimally and efficiently with a simple greedy strategy of taking items in order of value-to-weight ratio, in contrast to 0/1 knapsack where greedy strategies don't guarantee an optimal answer. Unbounded knapsack allows unlimited copies of each item. Beyond its role as a teaching problem, knapsack-style optimization appears directly in resource allocation problems such as budget allocation across competing projects, cargo loading and logistics, portfolio selection under a fixed capital constraint, and cutting stock problems in manufacturing, making it one of the more practically relevant classic algorithms problems rather than a purely academic exercise.
Key Concepts
- Selects items with weight and value to maximize value under a fixed capacity
- 0/1 variant: each item either fully included or excluded, no duplicates
- Solved via dynamic programming with a table indexed by item count and capacity
- Pseudo-polynomial O(n·W) time complexity, not truly polynomial in input size
- 0/1 knapsack is NP-complete in its general formulation
- Fractional knapsack variant solved optimally with a greedy value-to-weight strategy
- Unbounded knapsack variant allows unlimited copies of each item
- Greedy approaches fail to guarantee optimality for the 0/1 variant