text: The "quadratic" form of this problem, subject to binary and linear constraints, was first described by Gallo, Hammer, and Simeone in 1980.
full_question: The "quadratic" form of this problem, subject to binary and linear constraints, was first described by Gallo, Hammer, and Simeone in 1980. Finding the solution to this problem is necessary for finding the key in a Merkle-Hellman cryptosystem. A fully polynomial time approximation scheme for solving this problem is called the "one plus the error" method and has a runtime of "big o of n to the 2 to the one over the error." George Dantzig created a greedy algorithm to solve this problem that works by creating a ratio then choosing the items with the lowest ratio. That algorithm was created for the "unbounded" form of this problem; however, the "0-1" version of this problem is much more common. This problem, which can be solved in pseudo-polynomial time by dynamic programming, is NP-complete in its "decision form." For 10 points, name this problem which attempts to maximize profit at a certain weight limit as items are placed in a bag.
first_sentence: The "quadratic" form of this problem, subject to binary and linear constraints, was first described by Gallo, Hammer, and Simeone in 1980.
raw_answer: knapsack problem [or rucksack problem]