Problem: Please implement a function which gets the minimal number of coins, whose value is v_{1}, v_{2}, …, v_{n}, to make change for an amount of money with value t. Any coin with value v_{i} may duplicate for any times to make change.
For example, the minimal number of coins to make change for 15 out of a set of coins with value 1, 3, 9, 10 is 3. We can choose two coins with value 3 and a coin with value 9. The number of coins for other choices should be greater than 3.
Analysis: Firstly let us define a function f(t) which is the minimal number of coins to make change for total value t. If there are n different coins, we have n choices to make change for value t: we can add a coin with value v_{1} into a set of coins whose total value is tv_{1}. The minimal number of coins to get value tv_{1} is f(tv_{1}). Similarly, we can add a coin with value v_{2} into a set of coins whose total value is tv_{2}. The minimal number of coins to get value tv_{2} is f(tv_{2})…
Therefore, we divide a problem to calculate f(t) into n subproblems: f(tv_{1}), f(tv_{2}), …, f(tv_{n}). We can get a formal equation for f(t) as the following accordingly:
This equation can be implemented with recursion easily. However, the recursive solution will cause serious performance issues since there are overlaps when we divide this problem into n subproblems. A better solution is to utilize iteration, and store the result of subproblems into a table (as the Table 1).
In the Table 1, each column except the first one is to denote the number of coins to make change for a specific value. We can calculate the numbers in the Table 1 from left to right, to simulate the iterative process to get the result of f(15).
For instance, there are two numbers 4 and 2 under the column title “6”. We have two alternatives to make change for 6: the first one is to add a coin with value 1 to a set of coins whose total value is 5. Since the minimal number of coins to get value 5 is 3 (highlighted number under the column tile “5”), the number in the first cell under column title “6” is 4 (4=3+1). The second choice is to add a coin with value 3 to a set of coins whose total value is 3. Since the minimal number of coins to get value 3 is 1 (highlighted number under the column tile “3”), the number in the second cell under column title “6” is 2 (2=1+1). We highlight the number 2 in the column under tile 6 because 2 is less than 4.
0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15


1

0

1

2

3

2

3

4

3

4

5

2

2

3

3

4

5

3

0

–

–

1

2

3

2

3

4

3

4

5

2

2

3

3

9

0

–

–

–

–

–

–

–

–

1

2

3

2

3

4

3

10

0

–

–

–

–

–

–

–

–

–

1

2

3

2

3

4

Table 1: The iterative process to calculate the minimal number of coins to make changes for 15.
Even though we have a 2D matrix to show the iterative process, it only requires a 1D array for coding, because it is only necessary to store the minimal number of coins to make change for each total value. The sample code is shown below:
int GetMinCount(int total, int coins[], int length)
{
int* counts = new int[total + 1];
counts[0] = 0;
const int MAX = 0x7FFFFFFF;
for(int i = 1; i <= total; ++ i)
{
int count = MAX;
for(int j = 0; j < length; ++ j)
{
if(i – coins[j] >= 0 && count > counts[i – coins[j]])
count = counts[i – coins[j]];
}
if(count < MAX)
counts[i] = count + 1;
else
counts[i] = MAX;
}
int minCount = counts[total];
delete[] counts;
return minCount;
}
Advertisements