Knapsack problem
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.
[2] 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,[3] selection of investments and portfolios,[4] selection of assets for asset-backed securitization,[5] and generating keys for the Merkle–Hellman[6] 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.
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 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 that the only restriction on
One theme in research literature is to identify what the "hard" instances of the knapsack problem look like,[9][10] 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.
[11] The goal in finding these "hard" instances is for their use in public-key cryptography systems, such as the Merkle–Hellman knapsack cryptosystem.
[12] However, in the case of rational weights and profits it still admits a fully polynomial-time approximation scheme.
The NP-hardness of the Knapsack problem relates to computational models in which the size of integers matters (such as the Turing machine).
An upper bound for a decision-tree model was given by Meyer auf der Heide[17] who showed that for every n there exists an O(n4)-deep linear decision tree that solves the subset-sum problem with n items.
[11][20][21][22] The unbounded knapsack problem (UKP) places no restriction on the number of copies of each kind of item.
A similar dynamic programming solution for the 0-1 knapsack problem also runs in pseudo-polynomial time.
(If we only need the value m[n,W], we can modify the code so that the amount of memory required is O(W) which stores the recent two lines of the array "m".)
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
To be exact, the knapsack problem has a fully polynomial time approximation scheme (FPTAS).
[26] George Dantzig proposed a greedy approximation algorithm to solve the unbounded knapsack problem.
Nevertheless, a simple modification allows us to solve this case: Assume for simplicity that all items individually fit in the sack (
It can be shown that the average performance converges to the optimal solution in distribution at the error rate
[28] 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.
The Knapsack Hamiltonian is constructed via embedding the constraint condition to the cost function of the problem with a penalty term.
Solving the unbounded knapsack problem can be made easier by throwing away items which will never be needed.
Finding dominance relations allows us to significantly reduce the size of the search space.
Each comedian has a weight, brings in business based on their popularity and asks for a specific salary.
Such instances occur, for example, when scheduling packets in a wireless network with relay nodes.
[33] The algorithm from[33] also solves sparse instances of the multiple choice variant, multiple-choice multi-dimensional knapsack.
This variation is used in many loading and scheduling problems in Operations Research and has a Polynomial-time approximation scheme.
Han, Kawase and Makino[40] present a randomized algorithm for the unweighted non-removable setting.
For the unweighted removable setting, they give an 10/7-competitive-ratio algorithm, and prove a lower bound of 1.25.
(Solution: if any number of each book is available, then three yellow books and three grey books; if only the shown books are available, then all except for the green book.)
