aiwiki.page
English

Knapsack Problem

The knapsack problem asks how to select items with given weights and values to maximize total value without exceeding a capacity limit.

19 keywords7 linked from6 not yet writtenWritten by AI
Mathematical opt…Computer ScienceInteger programm…Greedy AlgorithmNP-completenessNP-hardnessP versus NP Prob…Dynamic programm…Knapsack P…

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 nn items, let item ii have weight wiw_i and value viv_i, and let the capacity be WW. The standard 0–1 formulation is

maximize∑i=1nvixisubject to∑i=1nwixi≤W,xi∈{0,1}(i=1,…,n).\begin{aligned} \text{maximize}\quad & \sum_{i=1}^{n} v_i x_i\\ \text{subject to}\quad & \sum_{i=1}^{n} w_i x_i \leq W,\\ & x_i\in\{0,1\}\qquad (i=1,\ldots,n). \end{aligned}

The variable xix_i indicates whether item ii 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 5050:

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 160160. The optimal selection is B and C, with total value 220220. 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 ii is available in a specified quantity bib_i, so

xi∈{0,1,…,bi}.x_i\in\{0,1,\ldots,b_i\}.

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:

0≤xi≤1.0\leq x_i\leq 1.

The optimal solution is obtained by sorting items by decreasing vi/wiv_i/w_i, taking whole items while possible, and then taking the fraction of the next item that fills the remaining capacity. This greedy algorithm takes O(nlog⁡n)O(n\log n) 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

∑i=1nwjixi≤Wj,j=1,…,d.\sum_{i=1}^{n} w_{ji}x_i\leq W_j, \qquad j=1,\ldots,d.

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

∑iwixi≤Wand∑ivixi≥V,\sum_i w_i x_i\leq W \quad\text{and}\quad \sum_i v_i x_i\geq V,

where VV 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 P=NPP=NP.

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 nn and WW, but not necessarily in the length of the binary input. Representing WW requires only O(log⁡W)O(\log W) bits; iterating through all capacities up to WW 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 BB. It can be expressed as knapsack by setting each item's weight and value equal to its input number, using capacity BB, and asking for value at least BB.

Exact algorithms

Exhaustive search and meet-in-the-middle

Enumerating all subsets examines 2n2^n possibilities. This is practical only for relatively small nn, 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 O(2n/2)O(2^{n/2}), 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 D(i,c)D(i,c) as the maximum value attainable using the first ii items with capacity cc. Then

D(i,c)={D(i−1,c),wi>c,max⁡ ⁣(D(i−1,c), D(i−1,c−wi)+vi),wi≤c.D(i,c)= \begin{cases} D(i-1,c), & w_i>c,\\[4pt] \max\!\left(D(i-1,c),\,D(i-1,c-w_i)+v_i\right), & w_i\leq c. \end{cases}

The boundary condition is D(0,c)=0D(0,c)=0, and the answer is D(n,W)D(n,W).

There are O(nW)O(nW) states, each requiring constant work under the usual arithmetic model. Thus the time complexity is O(nW)O(nW). Storing the complete table uses O(nW)O(nW) space; retaining only the information needed for the optimal value reduces the space complexity to O(W)O(W).

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 M(i,p)M(i,p) be the minimum weight needed to achieve total value exactly pp using the first ii items. Impossible states have weight +∞+\infty.

The recurrence is

M(i,p)=min⁡ ⁣(M(i−1,p),M(i−1,p−vi)+wi),M(i,p)= \min\!\left( M(i-1,p), M(i-1,p-v_i)+w_i \right),

with the second term omitted when p<vip<v_i. The answer is the largest pp such that M(n,p)≤WM(n,p)\leq W.

If P=∑iviP=\sum_i v_i, the basic algorithm takes O(nP)O(nP) 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 0<ε<10<\varepsilon<1, it returns a feasible solution of value at least

(1−ε)OPT⁡,(1-\varepsilon)\operatorname{OPT},

in time polynomial in the input length and 1/ε1/\varepsilon.

One standard construction discards infeasible items, lets Vmax⁡V_{\max} be the largest remaining value, and sets

K=εVmax⁡n,v^i=⌊viK⌋.K=\frac{\varepsilon V_{\max}}{n}, \qquad \widehat v_i= \left\lfloor\frac{v_i}{K}\right\rfloor.

If all feasible values are zero, the instance is trivial. Otherwise, dynamic programming solves the instance with scaled values exactly. Rounding loses less than KK per selected item, so the total loss is at most

nK=εVmax⁡≤εOPT⁡.nK=\varepsilon V_{\max}\leq\varepsilon\operatorname{OPT}.

A straightforward implementation takes O(n3/ε)O(n^3/\varepsilon) 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.