Knapsack problem

The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. The problem often arises in resource allocation where the decision makers have to choose from a set of non-divisible projects or tasks under a fixed budget or time constraint, respectively.
The knapsack problem has been studied for more than a century, with early works dating as far back as 1897. The name "knapsack problem" dates back to the early works of the mathematician Tobias Dantzig (1884–1956), and refers to the commonplace problem of packing the most valuable or useful items without overloading the luggage.
Applications.
Knapsack problems appear in real-world decision-making processes in a wide variety of fields, such as finding the least wasteful way to cut raw materials, selection of investments and portfolios, selection of assets for asset-backed securitization, and generating keys for the Merkle–Hellman and other knapsack cryptosystems.
One early application of knapsack algorithms was in the construction and scoring of tests in which the test-takers have a choice as to which questions they answer. For small examples, it is a fairly simple process to provide the test-takers with such a choice. For example, if an exam contains 12 questions each worth 10 points, the test-taker need only answer 10 questions to achieve a maximum possible score of 100 points. However, on tests with a heterogeneous distribution of point values, it is more difficult to provide choices. Feuerman and Weiss proposed a system in which students are given a heterogeneous test with a total of 125 possible points. The students are asked to answer all of the questions to the best of their abilities. Of the possible subsets of problems whose total point values add up to 100, a knapsack algorithm would determine which subset gives each student the highest possible score.
A 1999 study of the Stony Brook University Algorithm Repository showed that, out of 75 algorithmic problems, the knapsack problem was the 19th most popular and the third most needed after suffix trees and the bin packing problem.
Definition.
The most common problem being solved is the 0-1 knapsack problem, which restricts the number "formula_1" of copies of each kind of item to zero or one. Given a set of "formula_2" items numbered from 1 up to "formula_2", each with a weight "formula_4" and a value "formula_5", along with a maximum weight capacity "formula_6",
Here "formula_1" represents the number of instances of item "formula_11" to include in the knapsack. Informally, the problem is to maximize the sum of the values of the items in the knapsack so that the sum of the weights is less than or equal to the knapsack's capacity.
The bounded knapsack problem (BKP) removes the restriction that there is only one of each item, but restricts the number formula_1 of copies of each kind of item to a maximum non-negative integer value formula_13:
The unbounded knapsack problem (UKP) places no upper bound on the number of copies of each kind of item and can be formulated as above except for that the only restriction on formula_1 is that it is a non-negative integer.
One example of the unbounded knapsack problem is given using the figure shown at the beginning of this article and the text "if any number of each box is available" in the caption of that figure.
Computational complexity.
The knapsack problem is interesting from the perspective of computer science for many reasons:
There is a link between the "decision" and "optimization" problems in that if there exists a polynomial algorithm that solves the "decision" problem, then one can find the maximum value for the optimization problem in polynomial time by applying this algorithm iteratively while increasing the value of k. On the other hand, if an algorithm finds the optimal value of the optimization problem in polynomial time, then the decision problem can be solved in polynomial time by comparing the value of the solution output by this algorithm with the value of k. Thus, both versions of the problem are of similar difficulty.
One theme in research literature is to identify what the "hard" instances of the knapsack problem look like, or viewed another way, to identify what properties of instances in practice might make them more amenable than their worst-case NP-complete behaviour suggests. The goal in finding these "hard" instances is for their use in public key cryptography systems, such as the Merkle-Hellman knapsack cryptosystem.
Furthermore, notable is the fact that the hardness of the knapsack problem depends on the form of the input. If the weights and profits are given as integers, it is weakly NP-complete, while it is strongly NP-complete if the weights and profits are given as rational numbers. However, in the case of rational weights and profits it still admits a fully polynomial-time approximation scheme.
Solving.
Several algorithms are available to solve knapsack problems, based on the dynamic programming approach, the branch and bound approach or hybridizations of both approaches.
Dynamic programming in-advance algorithm.
The unbounded knapsack problem (UKP) places no restriction on the number of copies of each kind of item. Besides, here we assume that formula_21
Observe that formula_25 has the following properties:
1. formula_26 (the sum of zero items, i.e., the summation of the empty set).
2. formula_27
, formula_28, where formula_5 is the value of the formula_11-th kind of item.
The second property needs to be explained in detail. During the process of the running of this method, how do we get the weight formula_31? There are only formula_11 ways and the previous weights are formula_33 where there are total formula_11 kinds of different item (by saying different, we mean that the weight and the value are not completely the same). If we know each value of these formula_11 items and the related maximum value previously, we just compare them to each other and get the maximum value ultimately and we are done.
Here the maximum of the empty set is taken to be zero. Tabulating the results from formula_36 up through formula_37 gives the solution. Since the calculation of each formula_25 involves examining at most formula_2 items, and there are at most formula_6 values of formula_25 to calculate, the running time of the dynamic programming solution is formula_42. Dividing formula_43 by their greatest common divisor is a way to improve the running time.
Even if P≠NP, the formula_42 complexity does not contradict the fact that the knapsack problem is NP-complete, since formula_6, unlike formula_2, is not polynomial in the length of the input to the problem. The length of the formula_6 input to the problem is proportional to the number of bits in formula_6, formula_49, not to formula_6 itself. However, since this runtime is pseudopolynomial, this makes the (decision version of the) knapsack problem a weakly NP-complete problem.
0-1 knapsack problem.
A similar dynamic programming solution for the 0-1 knapsack problem also runs in pseudo-polynomial time. Assume formula_51 are strictly positive integers. Define formula_52 to be the maximum value that can be attained with weight less than or equal to formula_31 using items up to formula_11 (first formula_11 items).
We can define formula_52 recursively as follows: (Definition A)
The solution can then be found by calculating formula_62. To do this efficiently, we can use a table to store previous computations.
The following is pseudocode for the dynamic program:
// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
// NOTE: The array "v" and array "w" are assumed to store all relevant values starting at index 1.
array m[0..n, 0..W];
for j from 0 to W do:
 m[0, j] := 0
for i from 1 to n do:
 m[i, 0] := 0
for i from 1 to n do:
 for j from 0 to W do:
 if w[i] > j then:
 m[i, j] := m[i-1, j]
 else:
 m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
This solution will therefore run in formula_42 time and formula_42 space. 
However, if we take it a step or two further, we should know that the method will run in the time between formula_42 and formula_66. From Definition A, we can know that there is no need for computing all the weights when the number of items and the items themselves that we chose are fixed. That is to say, the program above computes more than necessary because that the weight changes from 0 to W all the time. From this perspective, we can program this method so that it runs recursively.
// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
// NOTE: The array "v" and array "w" are assumed to store all relevant values starting at index 1.
Define value[n, W]
Initialize all value[i, j] = -1
Define m:=(i,j) // Define function m so that it represents the maximum value we can get under the condition: use first i items, total weight limit is j
 if i == 0 or j <= 0 then:
 value[i, j] = 0
 return
 if (value[i-1, j] == -1) then: // m[i-1, j] has not been calculated, we have to call function m
 value[i-1, j] = m(i-1, j)
 if w[i] > j then: // item cannot fit in the bag
 value[i, j] = value[i-1, j]
 else: 
 if (value[i-1, j-w[i]] == -1) then: // m[i-1,j-w[i]] has not been calculated, we have to call function m
 value[i-1, j-w[i]] = m(i-1, j-w[i])
 value[i, j] = max(value[i-1,j], value[i-1, j-w[i]] + v[i])
Run m(n, W)
For example, there are 10 different items and the weight limit is 67. So,
If you use above method to compute for formula_68, you will get this, excluding calls that produce formula_69:
Besides, we can break the recursion and convert it into a tree. Then we can cut some leaves and use parallel computing to expedite the running of this method.
To find the actual subset of items, rather than just their total value, we can run this after running the function above:
 * Returns the indices of the items of the optimal knapsack.
 * i: We can include items 1 through i in the knapsack
 * j: maximum weight of the knapsack
function knapsack(i: int, j: int): Set<int> {
 if i == 0 then:
 if m[i, j] > m[i-1, j] then:
 return {i} ∪ knapsack(i-1, j-w[i])
 else:
 return knapsack(i-1, j)
knapsack(n, W)
Meet-in-the-middle.
Another algorithm for 0-1 knapsack, discovered in 1974 and sometimes called "meet-in-the-middle" due to parallels to a similarly named algorithm in cryptography, is exponential in the number of different items but may be preferable to the DP algorithm when formula_6 is large compared to "n". In particular, if the formula_4 are nonnegative but not integers, we could still use the dynamic programming algorithm by scaling and rounding (i.e. using fixed-point arithmetic), but if the problem requires formula_73 fractional digits of precision to arrive at the correct answer, formula_6 will need to be scaled by formula_75, and the DP algorithm will require formula_76 space and formula_77 time.
 algorithm Meet-in-the-middle is
 input: A set of items with weights and values.
 output: The greatest combined value of a subset.
 partition the set {1..."n"} into two sets "A" and "B" of approximately equal size
 compute the weights and values of all subsets of each set
 for each subset of "A" do
 find the subset of "B" of greatest value such that the combined weight is less than "W"
 keep track of the greatest combined value seen so far
The algorithm takes formula_78 space, and efficient implementations of step 3 (for instance, sorting the subsets of B by weight, discarding subsets of B which weigh more than other subsets of B of greater or equal value, and using binary search to find the best match) result in a runtime of formula_79. As with the meet in the middle attack in cryptography, this improves on the formula_80 runtime of a naive brute force approach (examining all subsets of formula_81), at the cost of using exponential rather than constant space (see also baby-step giant-step).
Approximation algorithms.
As for most NP-complete problems, it may be enough to find workable solutions even if they are not optimal. Preferably, however, the approximation comes with a guarantee of the difference between the value of the solution found and the value of the optimal solution.
As with many useful but computationally complex algorithms, there has been substantial research on creating and analyzing algorithms that approximate a solution. The knapsack problem, though NP-Hard, is one of a collection of algorithms that can still be approximated to any specified degree. This means that the problem has a polynomial time approximation scheme. To be exact, the knapsack problem has a fully polynomial time approximation scheme (FPTAS).
Greedy approximation algorithm.
George Dantzig proposed a greedy approximation algorithm to solve the unbounded knapsack problem. His version sorts the items in decreasing order of value per unit of weight, formula_82. It then proceeds to insert them into the sack, starting with as many copies as possible of the first kind of item until there is no longer space in the sack for more. Provided that there is an unlimited supply of each kind of item, if formula_83 is the maximum value of items that fit into the sack, then the greedy algorithm is guaranteed to achieve at least a value of formula_84.
For the bounded problem, where the supply of each kind of item is limited, the above algorithm may be far from optimal. Nevertheless, a simple modification allows us to solve this case: Assume for simplicity that all items individually fit in the sack (formula_85 for all formula_11). Construct a solution formula_87 by packing items greedily as long as possible, i.e. formula_88 where formula_89. Furthermore, construct a second solution formula_90 containing the first item that did not fit. Since formula_91 provides an upper bound for the LP relaxation of the problem, one of the sets must have value at least formula_84; we thus return whichever of formula_87 and formula_94 has better value to obtain a formula_95-approximation.
Fully polynomial time approximation scheme.
The fully polynomial time approximation scheme (FPTAS) for the knapsack problem takes advantage of the fact that the reason the problem has no known polynomial time solutions is because the profits associated with the items are not restricted. If one rounds off some of the least significant digits of the profit values then they will be bounded by a polynomial and 1/ε where ε is a bound on the correctness of the solution. This restriction then means that an algorithm can find a solution in polynomial time that is correct within a factor of (1-ε) of the optimal solution.
 algorithm FPTAS is 
 input: ε ∈ (0,1]
 a list A of n items, specified by their values, formula_5, and weights
 output: S' the FPTAS solution
 P := max formula_97 // the highest item value
 K := ε formula_98
 for i from 1 to n do
 formula_99 := formula_100
 end for
 return the solution, S', using the formula_99 values in the dynamic program outlined above
Theorem: The set formula_102 computed by the algorithm above satisfies formula_103, where formula_104 is an optimal solution.
Dominance relations.
Solving the unbounded knapsack problem can be made easier by throwing away items which will never be needed. For a given item formula_11, suppose we could find a set of items formula_106 such that their total weight is less than the weight of formula_11, and their total value is greater than the value of formula_11. Then formula_11 cannot appear in the optimal solution, because we could always improve any potential solution containing formula_11 by replacing formula_11 with the set formula_106. Therefore, we can disregard the formula_11-th item altogether. In such cases, formula_106 is said to dominate formula_11. (Note that this does not apply to bounded knapsack problems, since we may have already used up the items in formula_106.)
Finding dominance relations allows us to significantly reduce the size of the search space. There are several different types of dominance relations, which all satisfy an inequality of the form:
formula_117, and formula_118 for some formula_119
where
formula_120 and formula_121. The vector formula_122 denotes the number of copies of each member of formula_106.
Variations.
There are many variations of the knapsack problem that have arisen from the vast number of applications of the basic problem. The main variations occur by changing the number of some problem parameter such as the number of items, number of objectives, or even the number of knapsacks.
Multi-objective knapsack problem.
This variation changes the goal of the individual filling the knapsack. Instead of one objective, such as maximizing the monetary profit, the objective could have several dimensions. For example, there could be environmental or social concerns as well as economic goals. Problems frequently addressed include portfolio and transportation logistics optimizations.
As an example, suppose you ran a cruise ship. You have to decide how many famous comedians to hire. This boat can handle no more than one ton of passengers and the entertainers must weigh less than 1000 lbs. Each comedian has a weight, brings in business based on their popularity and asks for a specific salary. In this example, you have multiple objectives. You want, of course, to maximize the popularity of your entertainers while minimizing their salaries. Also, you want to have as many entertainers as possible.
Multi-dimensional knapsack problem.
In this variation, the weight of knapsack item formula_11 is given by a D-dimensional vector formula_171 and the knapsack has a D-dimensional capacity vector formula_172. The target is to maximize the sum of the values of the items in the knapsack so that the sum of weights in each dimension formula_73 does not exceed formula_174.
Multi-dimensional knapsack is computationally harder than knapsack; even for formula_175, the problem does not have EPTAS unless Pformula_176NP. However, the algorithm in is shown to solve sparse instances efficiently. An instance of multi-dimensional knapsack is sparse if there is a set formula_177 for formula_178 such that for every knapsack item formula_11, formula_180 such that formula_181 and formula_182. Such instances occur, for example, when scheduling packets in a wireless network with relay nodes. The algorithm from also solves sparse instances of the multiple choice variant, multiple-choice multi-dimensional knapsack.
The IHS (Increasing Height Shelf) algorithm is optimal for 2D knapsack (packing squares into a two-dimensional unit size square): when there are at most five square in an optimal packing.
Multiple knapsack problem.
This variation is similar to the Bin Packing Problem. It differs from the Bin Packing Problem in that a subset of items can be selected, whereas, in the Bin Packing Problem, all items have to be packed to certain bins. The concept is that there are multiple knapsacks. This may seem like a trivial change, but it is not equivalent to adding to the capacity of the initial knapsack. This variation is used in many loading and scheduling problems in Operations Research and has a Polynomial-time approximation scheme.
Quadratic knapsack problem.
The quadratic knapsack problem maximizes a quadratic objective function subject to binary and linear capacity constraints. The problem was introduced by Gallo, Hammer, and Simeone in 1980, however the first treatment of the problem dates back to Witzgall in 1975.
Subset-sum problem.
The subset sum problem is a special case of the decision and 0-1 problems where each kind of item, the weight equals the value: formula_183. In the field of cryptography, the term "knapsack problem" is often used to refer specifically to the subset sum problem and is commonly known as one of Karp's 21 NP-complete problems.
The generalization of subset sum problem is called multiple subset-sum problem, in which multiple bins exist with the same capacity. It has been shown that the generalization does not have an FPTAS.
Geometric knapsack problem.
In the geometric knapsack problem, there is a set of rectangles with different values, and a rectangular knapsack. The goal is to pack the largest possible value into the knapsack.