Problem:
While exploring a cave, Carl comes across a collection of 5-pound rocks worth each, 4-pound rocks worth each, and 1-pound rocks worth each. There are at least 20 of each size. He can carry at most 18 pounds. What is the maximum value, in dollars, of the rocks he can carry out of the cave?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
The 5 -pound rocks have a value of per pound; the 4 -pound rocks have a value of per pound; the 1-pound rocks have a value of per pound. It is not to Carl's advantage to take 1-pound rocks when he can take the larger rocks. Therefore the only issue is how many of the more valuable 5 -pound rocks to take, including as many 4-pound rocks as possible in each case. The viable choices are displayed in the following table.
The maximum possible value is .
Note: Although the 5-pound rocks are the most valuable per pound, it was not to Carl's advantage to take as many of them as possible. This situation is an example of the classic knapsack problem for which the so-called "greedy algorithm" is not optimal.
The problems on this page are the property of the MAA's American Mathematics Competitions