December 4, 2011
HomeAlgorithms and Data StructuresMaking change problem dynamic programming example

Making change problem dynamic programming example

By  Algorithms and Data Structures, Articles and Tutorials  1 Comment

Dynamic programming making change algorithm

Today we are going to discuss a new problem that can be solved using Dynamic Programming technique. We will talk about the well known problem of making change using a minimum number of coins. If you take the US currency as an example where we have the denominations (1C, 5C, 10C, 25C) then this problem can be easily solved using a greedy approach. For more information about a greedy solution for this particular case you can refer to the following post. What we are discussing today (however) is the general form of making change problem. If we have a different set of coins (different values) then greedy algorithm might not work as we might expect. On the other hand Dynamic Programming is guaranteed to give an optimal solution so let us get started.

Problem Definition

Given a set of coin denominations (V1 = 1, V2, V3, …, Vn) and an amount of money (C). Make change for the given amount of money using a minimum number of coins. For example if the set of coins is (1, 3, 6, 7) and the amount of money is (9) then the solution is (6, 3) however if you use a greedy approach then you will choose (7, 1, 1). It is obvious that the greedy solution is not optimal as (3 > 2)

Change making problem dynamic programming solution

Let the minimum number of coins needed to make change for an amount of money (j) be M(j) so:

C++
1
2
3
4
5
6
7
8
9
M(1) = 1 and the solution is [1]
M(2) = 2 and the solution is [1, 1]
M(3) = 1 and the solution is [3]
M(4) = 2 and the solution is [1, 3]
M(5) = 3 and the solution is [1, 1, 3]
M(6) = 1 and the solution is [6]
M(7) = 1 and the solution is [7]
M(8) = 2 and the solution is [1, 7]
M(9) = 2 and the solution is [3, 6]

The general formula for M(j) is:

C++
1
2
3
M(0) = 0
M(j) = 1 + MIN (M(j-Vi))
where (1 <= i <= n) and (j-Vi >= 0) and (j <= C)

Let us apply the formula and see how it works:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
M(1) = 1 + MIN (M(1-1))
     = 1 + MIN (M(0))
     = 1 + 0
     = 1
 
M(2) = 1 + MIN (M(2-1))
     = 1 + MIN (M(1))
     = 1 + MIN (1)
     = 2
 
M(3) = 1 + MIN (M(3-1), M(3-3))
     = 1 + MIN (M(2), M(0))
     = 1 + MIN (2, 0)
     = 1
 
M(4) = 1 + MIN (M(4-1), M(4-3))
     = 1 + MIN (M(3), M(1))
     = 1 + MIN (1, 1)
     = 2
 
M(5) = 1 + MIN (M(5-1), M(5-3))
     = 1 + MIN (M(4), M(2))
     = 1 + MIN (2, 2)
     = 3
 
M(6) = 1 + MIN (M(6-1), M(6-3), M(6-6))
     = 1 + MIN (M(5), M(3), M(0))
     = 1 + MIN (3, 1, 0)
     = 1
 
M(7) = 1 + MIN (M(7-1), M(7-3), M(7-6), M(7-7))
     = 1 + MIN (1, 2, 1, 0)
     = 1
 
M(8) = 1 + MIN (M(8-1), M(8-3), M(8-6), M(8-7))
     = 1 + MIN (1, 3, 2, 1)
     = 2
 
M(9) = 1 + MIN (M(9-1), M(9-3), M(9-6), M(9-7))
     = 1 + MIN (2, 1, 1, 2)
     = 2

As you can see this magical formula really works so where is the magic. Take a look at the following diagram to help you visualize what is going on:

Let us try to explain that in plain English. Suppose that you made change for some amount using the minimum number of coins. If you take one of the coins out then the minimum number of coins needed to make that amount is one (the one you just took out) plus the minimum number of coins needed to make change for the remainder of the amount which is the difference between the amount and the taken coin value. Since the coin we take out from the amount can be any coin value (less than the amount of course otherwise you get a negative result which does not make sense) then we need to try all possible coin values we can take out then choose the one that gives us the minimum needed number of coins. We are now ready to formulate our solution so let us apply Dynamic Programming steps.

Characterize the structure of an optimal solution

I admit through out this series of articles on Dynamic Programming I used to mix the first two steps together. Characterizing the optimal structure of a given problem is not only identifying the value to be optimized but also describing its structure and how it relates to sub problems. The reason why I did that is (1) I reveal much of the structure of the optimal solution in the introduction (2) The recursive definition in the second step tells us more about the structure of an optimal solution. I will be following the same approach and if there is any confusion it should be cleared out by reading the article in full and by going through the series from the beginning. In this problem the value we are trying to optimize is the number of coins and we need to make this number the smallest possible. In the next section we will define the minimum number of coins needed in terms of smaller amounts using recursion. We almost explained everything in the example above so let us formulate that.

Recursively define the value of an optimal solution

Let us provide a making change recursive algorithm. Let the minimum number of coins needed to make change for an amount of money (j) be M(j). This can be recursively defined as:

C++
1
2
3
M(0) = 0
M(j) = 1 + MIN (M(j-Vi))
where (1 <= i <= n) and (j-Vi >= 0) and (0 <= j <= C)

Note that:

  1. (i) goes from (1) to (n) because we have (n) coin denominations (V1 .. Vn).
  2. (j-Vi >= 0) because money values can not be negative so we exclude those (Vi) values that yield negative value of (j-Vi).
  3. (0 <= j <= C) means (j) can be any values less than or equal to the money amount we need to make change for.
  4. Note also that sub problems are overlapping for example M(j-Vi) represents one or more values depending on the value of (i) but not all values are calculated every single time from the scratch. Values are saved in M(j) then looked up whenever needed. If you go back to the example we provided earlier at the beginning of this article you will notice that the values of M(j) repeat for example M(1) is used in both M(2) and M(4).

Once M(j) is fully populated (bottom up) we can just take M(C) to get the minimum number of coins needed to make the required change but this is going to be one part of the solution. The other part is printing out the actual coins used in making change for the input amount. This can be done using a back pointers array as we already learned from the previous articles. Let us define b(j) to mark the coin denomination (Vi) at which the number of coins M(j) is the minimum. We will use b(j) in the last step to construct the actual solution. In the following step will populate both tables (arrays) M(j) and b(j).

Compute the value of an optimal solution in a bottom up fashion

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//Making change coins algorithm:
//Number of coins to make an
//amount of zero is zero
M[0] = 0;
 
//Find the minimum number of coins needed
//to make change for each money amount (j)
//less than or equal to the input amount (C)
for (int j = 1; j <= C; j++)
{
//Initialize min to some big value
int min = 9999;
 
//By default initialize b[j] to the
//first value V[1] then this value
//will be updated later to the V[i]
//value that yields minimum number
//of coins
b[j] = V[1];
 
//Try to find the coin denomination
//that gives us the minimum number of
//coins needed to make change for money
//amount of (j)
for (int i = 1; i <= n; i++)
{
//Money amounts should not be negative.
//Keep checking all M[j-V[i]] until we
//find V[i] that gives us the minimum
//number of coins needed to make change
//for money amount of (j)
if (j-V[i] >= 0 && M[j-V[i]] < min])
{
//Update the min value
min = M[j-V[i]];
 
//Save the V[i] at which
//a minimum is found
b[j] = V[i];
}
}
 
//Apply the formula that we
//proved in the introduction
M[j] = 1 + min;
}
 
//Minimum number of coins to make change
//for money amount of (C) is M[C]
print ("Minimum number of coins to make change for amount C = ", M[C]);
print ("and here are the coins: ");
 
//Printing the actual coins is done in
//the next section. Here is the recursive
//function call
PrintCoins(b, C);

Construct an optimal solution from the computed information

Constructing the final solution which is printing the actual coin values needed to make change for a given amount of money is achieved by tracing back the back pointers array b[j]. Here is how we do it using recursion.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//The recursive function receives
//the back pointers array b[j] and
//money amount (j) as its input
PrintCoins(int b[], int j)
{
//This is the base case for recursion.
//We do nothing if the amount of money is 0
if (j == 0)
{
         return;
}
 
//Recall that b[j] stores the coin
//value V[i] that minimizes the number
//of coins needed to make change for money
//amount (j) so we print this value as the
//first coin we need
print b[j];
 
//Recursively call the function using the
//remainder amount which is (j-V[i]). Recall
//that V[i] is stored in b[j]
PrintCoins(b, j - b[j]);
}

We are done with part 7. In the next part I will explain the 7th Dynamic Programming problem “Edit Distance“.

Please use the comments section below for questions, corrections or feedback. Thanks for reading.

More from my site

Tags:, , ,

About Author

Mohammed Abualrob

Software Engineer @ Cisco

One Comment
  1. Abhishek singh

    🙂 😀 😆 please add more problem of dp ,,, your site is great,,, i love it …

    Reply

Add a Comment

Your email address will not be published. Required fields are marked *