The problem statement - producing coins
We'll begin by stating the problem to be solved.
Imagine that it is the end of the calendar year at the United States Mint. The Mint keeps an inventory of the various minerals used to produce the coins that are put into circulation, and it wants to use up the minerals on hand before retooling for next year's coins.
The Mint produces several different types of coins, each with a different composition. The table below shows the make-up of each coin type (as reported in the US Mint coin specifications).
| Penny | Nickel | Dime | Quarter | Dollar | |
| Copper (Cu) | 0.06g | 3.8g | 2.1g | 5.2g | 7.2g |
| Nickel (Ni) | 1.2g | 0.2g | 0.5g | 0.2g | |
| Zinc (Zi) | 2.4g | 0.5g | |||
| Manganese (Mn) | 0.3g |
Suppose the Mint wants to use the available materials to produce coins with the maximum total dollar value. Which coins should they produce?
