The knapsack problem is a problem in mathematical optimization: given items with specified weights and values, select a collection whose total weight does not exceed a capacity and whose total value is as large as possible. Its name evokes packing a bag with limited carrying capacity. The standard 0–1 knapsack problem allows each item to be selected at most once; other variants allow repeated items, divisible items, multiple bags, or several resource constraints. It is a central example in computer science because closely related versions range from efficiently solvable problems to computationally difficult ones.
Mathematical formulation
For items, let item have weight and value , and let the capacity be . The standard 0–1 formulation is
The variable indicates whether item is selected. This is a special case of integer programming, with one capacity constraint and binary decision variables.
Weights need not represent physical mass: they may represent cost, storage consumption, processing time, or another limited resource. Values may represent profit, utility, priority, or expected benefit.
The conventional algorithmic formulation assumes positive integer weights and nonnegative integer values, with numbers encoded in binary. Rational inputs can also be considered, but running times that depend on numerical magnitudes must then be interpreted carefully. An item heavier than the capacity can be discarded. In the ordinary model, a zero-weight item with positive value can be selected immediately.
For example, suppose the capacity is :
| Item | Weight | Value | Value-to-weight ratio |
|---|---|---|---|
| A | 10 | 60 | 6 |
| B | 20 | 100 | 5 |
| C | 30 | 120 | 4 |
Choosing items in decreasing value-to-weight order selects A and B, with total value . The optimal selection is B and C, with total value . This illustrates why a locally attractive choice need not produce the best indivisible selection.
Principal variants
0–1, bounded, and unbounded knapsack
In 0–1 knapsack, each item is either selected or omitted.
In bounded knapsack, item type is available in a specified quantity , so
In unbounded knapsack, any nonnegative integer number of copies may be taken. Positive weights ensure that only finitely many copies fit within a finite capacity. Bounded instances can be transformed into 0–1 instances by splitting quantities into groups, commonly using a binary grouping technique.
Although these variants resemble one another, they require different recurrence relations or update orders in memory-efficient implementations.
Fractional knapsack
In fractional knapsack, each item may be divided:
The optimal solution is obtained by sorting items by decreasing , taking whole items while possible, and then taking the fraction of the next item that fills the remaining capacity. This greedy algorithm takes time with comparison sorting.
Its correctness depends on divisibility: replacing a quantity of lower-ratio material with an equal weight of higher-ratio material cannot decrease value. This exchange argument does not apply to indivisible items.
Multiple constraints and multiple bags
In multidimensional knapsack, each item consumes several resources. The constraints take the form
For example, a project might consume both money and staff time. A capacity-indexed dynamic program then typically has a state space depending on the product of the capacities, which can become prohibitively large.
In multiple knapsack, items are assigned to several bags, each with its own capacity, and each item can ordinarily be assigned to at most one bag. This differs from multidimensional knapsack: several containers are not the same as several simultaneous resource limits on one selection.
Other extensions impose group choices, dependencies, conflicts between items, or nonlinear values. Such additions can substantially change the available algorithms and approximation guarantees.
Computational complexity
The optimization problem asks for a maximum-value feasible selection. Its decision version asks whether there is a selection satisfying both
where is a target value.
For binary-encoded integer inputs, this decision problem is NP-complete, and the optimization problem is NP-hard. A proposed selection can be checked efficiently, but no polynomial-time exact algorithm for all instances is known. Such an algorithm would resolve the P versus NP problem in favor of .
The standard problem is weakly NP-complete, reflecting its dependence on numerical magnitudes. It has a pseudo-polynomial-time algorithm whose running time is polynomial in and , but not necessarily in the length of the binary input. Representing requires only bits; iterating through all capacities up to can therefore require exponentially many steps relative to that representation.
The closely related subset sum problem asks whether some input numbers sum exactly to a target . It can be expressed as knapsack by setting each item's weight and value equal to its input number, using capacity , and asking for value at least .
Exact algorithms
Exhaustive search and meet-in-the-middle
Enumerating all subsets examines possibilities. This is practical only for relatively small , though pruning can reduce the work on particular instances.
A meet-in-the-middle algorithm splits the items into two groups and enumerates the weight–value pairs achievable in each group. After removing dominated pairs and sorting, it combines compatible choices from the two groups. Its running time is roughly , apart from polynomial factors, with substantial memory requirements.
This approach is useful when the number of items is moderate but the capacity is too large for a capacity-indexed table.
Dynamic programming by capacity
For integer weights, dynamic programming gives an exact method. Define as the maximum value attainable using the first items with capacity . Then
The boundary condition is , and the answer is .
There are states, each requiring constant work under the usual arithmetic model. Thus the time complexity is . Storing the complete table uses space; retaining only the information needed for the optimal value reduces the space complexity to .
A one-dimensional implementation updates capacities in descending order:
dp[0 ... W] = 0
for each item i:
for c from W down to w[i]:
dp[c] = max(dp[c], dp[c - w[i]] + v[i])
Descending order prevents the current item from being used more than once. Updating capacities in ascending order instead permits repeated use of that item and implements the corresponding unbounded-knapsack recurrence.
Recovering the selected items requires additional bookkeeping, a retained table, or a reconstruction procedure; an optimal-value array alone does not directly record the selection.
Dynamic programming by value
When values are small integers but weights are large, the roles of the two quantities can be reversed. Let be the minimum weight needed to achieve total value exactly using the first items. Impossible states have weight .
The recurrence is
with the second term omitted when . The answer is the largest such that .
If , the basic algorithm takes time. This formulation also provides a foundation for approximation by scaling values.
Branch-and-bound and optimization solvers
Branch-and-bound explores partial selections while discarding branches that cannot improve the best known feasible solution. Solving the fractional relaxation supplies an upper bound on the value obtainable from a branch.
Practical integer-programming solvers may combine such bounds with preprocessing, cutting planes, and specialized search. They can solve many substantial instances, but performance depends strongly on instance structure and does not remove the worst-case complexity.
Approximation algorithms
The standard 0–1 problem admits efficient approximation even though exact optimization is NP-hard.
A simple approximation algorithm first discards items heavier than the capacity and sorts the remaining items by value-to-weight ratio. It considers the whole-item prefix before the first item that would exceed capacity, and compares that prefix with the highest-value feasible single item. The better choice has value at least half the optimum.
The guarantee follows from the fractional relaxation: its value is at most the prefix value plus the full value of the first item that does not fit. Both quantities are bounded by the two candidate solutions being compared.
More strongly, 0–1 knapsack has a fully polynomial-time approximation scheme, or FPTAS. For any , it returns a feasible solution of value at least
in time polynomial in the input length and .
One standard construction discards infeasible items, lets be the largest remaining value, and sets
If all feasible values are zero, the instance is trivial. Otherwise, dynamic programming solves the instance with scaled values exactly. Rounding loses less than per selected item, so the total loss is at most
A straightforward implementation takes time under the standard arithmetic model. More advanced schemes improve this bound. These guarantees apply to the standard single-constraint problem and do not automatically carry over to its extensions.
Applications and modeling limits
Knapsack models arise in budget allocation, cargo selection, project selection, storage management, and resource-constrained scheduling. They also appear as subproblems inside larger optimization methods.
The basic model assumes that item values add independently and that resource consumption is known. It does not directly capture interactions such as two projects becoming valuable only when selected together, uncertain future costs, or priorities that cannot be represented by one numerical objective. Dependencies and multiple resources require explicit extensions.
Knapsack is related to, but distinct from, bin packing. Knapsack usually selects a valuable subset for limited capacity; bin packing normally assigns all items while minimizing the number of containers.
Knapsack-like problems have also been used in cryptography. Early proposals included public-key systems based on structured subset-sum instances. Several prominent early constructions were broken: the difficulty of general knapsack instances does not establish the security of a particular structured cryptographic construction.