Knapsack problem


The knapsack problem is the following problem in combinatorial optimization:
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 subset sum problem is a special case of the decision and 0-1 problems where for each kind of item, the weight equals the value:. In the field of cryptography, the term knapsack problem is often used to refer specifically to the subset sum problem. The subset sum problem is one of Karp's 21 NP-complete problems.

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 related to the field of combinatorial algorithms and algorithm engineering, 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 ' of copies of each kind of item to zero or one. Given a set of ' items numbered from 1 up to ', each with a weight ' and a value ', along with a maximum weight capacity ',
Here ' represents the number of instances of item ' 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 removes the restriction that there is only one of each item, but restricts the number of copies of each kind of item to a maximum non-negative integer value :
The unbounded knapsack problem 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 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 book 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. More generally, better understanding of the structure of the space of instances of an optimization problem helps to advance the study of the particular problem and can improve algorithm selection.
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.

Unit-cost models

The NP-hardness of the Knapsack problem relates to computational models in which the size of integers matters. In contrast, decision trees count each decision as a single step. Dobkin and Lipton show an lower bound on linear decision trees for the knapsack problem, that is, trees where decision nodes test the sign of affine functions. This was generalized to algebraic decision trees by Steele and Yao.
If the elements in the problem are real numbers or rationals, the decision-tree lower bound extends to the real random-access machine model with an instruction set that includes addition, subtraction and multiplication of real numbers, as well as comparison and either division or remaindering. This model covers more algorithms than the algebraic decision-tree model, as it encompasses algorithms that use indexing into tables. However, in this model all program steps are counted, not just decisions.
An upper bound for a decision-tree model was given by Meyer auf der Heide who showed that for every n there exists an -deep linear decision tree that solves the [|subset-sum problem] with n items. Note that this does not imply any upper bound for an algorithm that should solve the problem for any given n.

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 places no restriction on the number of copies of each kind of item. Besides, here we assume that
Observe that has the following properties:
1. .
2.
,, where is the value of the -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 ? There are only ways and the previous weights are where there are total kinds of different item. If we know each value of these 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 up through gives the solution. Since the calculation of each involves examining at most items, and there are at most values of to calculate, the running time of the dynamic programming solution is Big O notation|. Dividing by their greatest common divisor is a way to improve the running time.
Even if P≠NP, the complexity does not contradict the fact that the knapsack problem is NP-complete, since, unlike, is not polynomial in the length of the input to the problem. The length of the input to the problem is proportional to the number of bits in,, not to itself. However, since this runtime is pseudopolynomial, this makes 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 are strictly positive integers. Define to be the maximum value that can be attained with weight less than or equal to using items up to .
We can define recursively as follows:
  • if
  • if.
The solution can then be found by calculating. To do this efficiently, we can use a table to store previous computations.
The following is pseudocode for the dynamic program:

// Input:
// Values
// Weights
// Number of distinct items
// Knapsack capacity
// NOTE: The array "v" and array "w" are assumed to store all relevant values starting at index 1.
array m;
for j from 0 to W do:
m := 0
for i from 1 to n do:
m := 0
for i from 1 to n do:
for j from 1 to W do:
if w > j then:
m := m
else:
m := max

This solution will therefore run in time and space.
However, if we take it a step or two further, we should know that the method will run in the time between and. From Definition A, we know that there is no need to compute 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 the weight changes from 0 to W often. From this perspective, we can program this method so that it runs recursively.

// Input:
// Values
// Weights
// Number of distinct items
// Knapsack capacity
// NOTE: The array "v" and array "w" are assumed to store all relevant values starting at index 1.
Define value
Initialize all value = -1
Define m:= // 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
Run m

For example, there are 10 different items and the weight limit is 67. So,
If you use above method to compute for, you will get this, excluding calls that produce :
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: Set
knapsack