Editing Knapsack problem (section)

==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,<ref>{{cite book |last1=Kellerer |first1=Hans |last2=Pferschy |first2=Ulrich |last3=Pisinger |first3=David |title=Knapsack problems |date=2004 |publisher=Springer |location=Berlin |isbn=978-3-540-40286-2 |page=449 |url=https://books.google.com/books?id=u5DB7gck08YC |access-date=5 May 2022}}</ref> selection of [[fixed investment|investment]]s and [[Portfolio (finance)|portfolios]],<ref>{{cite book |last1=Kellerer |first1=Hans |last2=Pferschy |first2=Ulrich |last3=Pisinger |first3=David |title=Knapsack problems |date=2004 |publisher=Springer |location=Berlin |isbn=978-3-540-40286-2 |page=461 |url=https://books.google.com/books?id=u5DB7gck08YC |access-date=5 May 2022}}</ref> selection of assets for [[Securitization|asset-backed securitization]],<ref>{{cite book |last1=Kellerer |first1=Hans |last2=Pferschy |first2=Ulrich |last3=Pisinger |first3=David |title=Knapsack problems |date=2004 |publisher=Springer |location=Berlin |isbn=978-3-540-40286-2 |page=465 |url=https://books.google.com/books?id=u5DB7gck08YC |access-date=5 May 2022}}</ref> and generating keys for the [[Merkle–Hellman knapsack cryptosystem|Merkle–Hellman]]<ref>{{cite book |last1=Kellerer |first1=Hans |last2=Pferschy |first2=Ulrich |last3=Pisinger |first3=David |title=Knapsack problems |date=2004 |publisher=Springer |location=Berlin |isbn=978-3-540-40286-2 |page=472 |url=https://books.google.com/books?id=u5DB7gck08YC |access-date=5 May 2022}}</ref> 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.<ref>{{cite journal | title = A Mathematical Programming Model for Test Construction and Scoring | journal = Management Science | volume = 19 | issue = 8 |date = April 1973|pages = 961–966 |author1=Feuerman, Martin |author2=Weiss, Harvey | jstor = 2629127 | doi=10.1287/mnsc.19.8.961}}</ref>

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 tree]]s and the [[bin packing problem]].<ref>{{cite journal | title = Who is Interested in Algorithms and Why? Lessons from the Stony Brook Algorithm Repository | author = Skiena, S. S. |journal = ACM SIGACT News | volume = 30 | issue=3 |date = September 1999| pages= 65&ndash;74  |issn=0163-5700 | doi=10.1145/333623.333627| citeseerx = 10.1.1.41.8357 | s2cid = 15619060 }}</ref>