What is the smallest number of coins I could have?

Question

A country has 6 coins of the following denominations: 1 cent, 2 cents, 4 cents, 10 cents, 20 cents and 40 cents. Using the coins I have, I can pay exactly for any amount up to and including 200 cents. What is the smallest number of coins I could have?

Answer 1

You have to have a 1 cent coin so you can make 1. To make 3, you need either a 1 and a 2 or three ones. The first uses fewer coins. Keep going.

Answer 2

This looks very much like a knapsack problem.

If we are given a positive integer $n \leq 200$, then we solve the following integer program (IP) to determine how many coins of each denomination to pick

$$\begin{array}{ll} \text{minimize} & \displaystyle\sum_{i=1}^6 x_i\\ \text{subject to} & x_1 + 2 x_2 + 4 x_3 + 10 x_4 + 20 x_5 + 40 x_6 = n\\ & x_i \in \mathbb N\end{array}$$

where the decision variables are

• $x_1$ is the number of $1$ cent coins.
• $x_2$ is the number of $2$ cent coins.
• $x_3$ is the number of $4$ cent coins.
• $x_4$ is the number of $10$ cent coins.
• $x_5$ is the number of $20$ cent coins.
• $x_6$ is the number of $40$ cent coins.