Editing Knapsack problem (section)

{{Short description|Problem in combinatorial optimization}}
[[File:Knapsack Problem Illustration.svg|thumb|right|250px|Example of a one-dimensional (constraint) knapsack problem: which books should be chosen to maximize the amount of money while still keeping the overall weight under or equal to 15&nbsp;kg? A [[List of knapsack problems#Multiple constraints|multiple constrained problem]] could consider both the weight and volume of the books. <br />(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.)]]

The '''knapsack problem''' is the following problem in [[combinatorial optimization]]:
:''Given a set of items, each with a weight and a value, determine which items to include in the 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.<ref>{{cite journal | title = On the partition of numbers | author = Mathews, G. B. | journal = Proceedings of the London Mathematical Society | volume = 28 | pages = 486&ndash;490 | date = 25 June 1897 | url = http://plms.oxfordjournals.org/content/s1-28/1/486.full.pdf |doi = 10.1112/plms/s1-28.1.486}}</ref>

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: <math>w_i=v_i</math>.  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]].<ref>Richard M. Karp (1972). "[https://web.archive.org/web/20190608032217/https://pdfs.semanticscholar.org/a3c3/7657822859549cd6b12b0d1f76f8ee3680a0.pdf Reducibility Among Combinatorial Problems]". In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103</ref>