# Algorithm to Make Change in Python - Dynamic Programming

Making change is another common example of Dynamic Programming discussed in my algorithms classes. This is almost identical to the example earlier to solve the Knapsack Problem in Clash of Clans using Python, but it might be easier to understand for a common scenario of making change. Dynamic Programming is a good algorithm to use for problems that have overlapping sub-problems like this one. Just like with the Clash of Clans example, this is a discrete Knapsack problem allowing repetition.

## Make Change in Python

The goal is to minimize the number of dollar bills used to make change for a certain amount of money. The currency will be made up of \$1, \$5, \$10, \$20, \$50, and \$100 bills. In the Python script I am making change for \$120, but one can change the variable `amount` to any reasonable integer.

```# USD - \$1, \$5, \$10, etc.
currency = [1, 5, 10, 20, 50, 100]

# the amount to change - \$120
amount = 120
```

I keep track of the the minimum number of bills used to make change and the actual bills used to make that change in a couple of lists. The very first item in each list is initialized for the initial situation of making change for \$0. In the case of making change for \$0, we don't make any change. The minimum number of currency is 0 and the bills used is an empty list.

```# initialize arrays for \$0
minimum_number_of_currency = [0]
currency_composition = [[]]
```

The Python script to make change using Dynamic Programming is as follows:

```# USD - \$1, \$5, \$10, etc.
currency = [1, 5, 10, 20, 50, 100]

# the amount to change - \$120
amount = 120

# initialize arrays for \$0
minimum_number_of_currency = [0]
currency_composition = [[]]

for i in xrange(1, amount + 1):
best = 10000
best_currency_composition = None

for j in currency:
if i - j > -1 and minimum_number_of_currency[i - j] + 1 < best:
best = minimum_number_of_currency[i - j] + 1
best_currency_composition = currency_composition[i - j] + [j]

minimum_number_of_currency.append(best)
currency_composition.append(best_currency_composition)

print '{0:3} {1} {2}'.format(i, best, best_currency_composition)
```

Here is the output that shows the minimum number of bills and bills used to make change from \$1 to \$120. For example, I will need 2 bills to make \$120, a \$100 bill and a \$20 bill.

```  1 1 [1]
2 2 [1, 1]
3 3 [1, 1, 1]
4 4 [1, 1, 1, 1]
5 1 [5]
6 2 [5, 1]
7 3 [5, 1, 1]
8 4 [5, 1, 1, 1]
9 5 [5, 1, 1, 1, 1]
10 1 [10]
11 2 [10, 1]
12 3 [10, 1, 1]
13 4 [10, 1, 1, 1]
14 5 [10, 1, 1, 1, 1]
15 2 [10, 5]
16 3 [10, 5, 1]
17 4 [10, 5, 1, 1]
18 5 [10, 5, 1, 1, 1]
19 6 [10, 5, 1, 1, 1, 1]
20 1 [20]
21 2 [20, 1]
22 3 [20, 1, 1]
23 4 [20, 1, 1, 1]
24 5 [20, 1, 1, 1, 1]
25 2 [20, 5]
26 3 [20, 5, 1]
27 4 [20, 5, 1, 1]
28 5 [20, 5, 1, 1, 1]
29 6 [20, 5, 1, 1, 1, 1]
30 2 [20, 10]
31 3 [20, 10, 1]
32 4 [20, 10, 1, 1]
33 5 [20, 10, 1, 1, 1]
34 6 [20, 10, 1, 1, 1, 1]
35 3 [20, 10, 5]
36 4 [20, 10, 5, 1]
37 5 [20, 10, 5, 1, 1]
38 6 [20, 10, 5, 1, 1, 1]
39 7 [20, 10, 5, 1, 1, 1, 1]
40 2 [20, 20]
41 3 [20, 20, 1]
42 4 [20, 20, 1, 1]
43 5 [20, 20, 1, 1, 1]
44 6 [20, 20, 1, 1, 1, 1]
45 3 [20, 20, 5]
46 4 [20, 20, 5, 1]
47 5 [20, 20, 5, 1, 1]
48 6 [20, 20, 5, 1, 1, 1]
49 7 [20, 20, 5, 1, 1, 1, 1]
50 1 [50]
51 2 [50, 1]
52 3 [50, 1, 1]
53 4 [50, 1, 1, 1]
54 5 [50, 1, 1, 1, 1]
55 2 [50, 5]
56 3 [50, 5, 1]
57 4 [50, 5, 1, 1]
58 5 [50, 5, 1, 1, 1]
59 6 [50, 5, 1, 1, 1, 1]
60 2 [50, 10]
61 3 [50, 10, 1]
62 4 [50, 10, 1, 1]
63 5 [50, 10, 1, 1, 1]
64 6 [50, 10, 1, 1, 1, 1]
65 3 [50, 10, 5]
66 4 [50, 10, 5, 1]
67 5 [50, 10, 5, 1, 1]
68 6 [50, 10, 5, 1, 1, 1]
69 7 [50, 10, 5, 1, 1, 1, 1]
70 2 [50, 20]
71 3 [50, 20, 1]
72 4 [50, 20, 1, 1]
73 5 [50, 20, 1, 1, 1]
74 6 [50, 20, 1, 1, 1, 1]
75 3 [50, 20, 5]
76 4 [50, 20, 5, 1]
77 5 [50, 20, 5, 1, 1]
78 6 [50, 20, 5, 1, 1, 1]
79 7 [50, 20, 5, 1, 1, 1, 1]
80 3 [50, 20, 10]
81 4 [50, 20, 10, 1]
82 5 [50, 20, 10, 1, 1]
83 6 [50, 20, 10, 1, 1, 1]
84 7 [50, 20, 10, 1, 1, 1, 1]
85 4 [50, 20, 10, 5]
86 5 [50, 20, 10, 5, 1]
87 6 [50, 20, 10, 5, 1, 1]
88 7 [50, 20, 10, 5, 1, 1, 1]
89 8 [50, 20, 10, 5, 1, 1, 1, 1]
90 3 [50, 20, 20]
91 4 [50, 20, 20, 1]
92 5 [50, 20, 20, 1, 1]
93 6 [50, 20, 20, 1, 1, 1]
94 7 [50, 20, 20, 1, 1, 1, 1]
95 4 [50, 20, 20, 5]
96 5 [50, 20, 20, 5, 1]
97 6 [50, 20, 20, 5, 1, 1]
98 7 [50, 20, 20, 5, 1, 1, 1]
99 8 [50, 20, 20, 5, 1, 1, 1, 1]
100 1 [100]
101 2 [100, 1]
102 3 [100, 1, 1]
103 4 [100, 1, 1, 1]
104 5 [100, 1, 1, 1, 1]
105 2 [100, 5]
106 3 [100, 5, 1]
107 4 [100, 5, 1, 1]
108 5 [100, 5, 1, 1, 1]
109 6 [100, 5, 1, 1, 1, 1]
110 2 [100, 10]
111 3 [100, 10, 1]
112 4 [100, 10, 1, 1]
113 5 [100, 10, 1, 1, 1]
114 6 [100, 10, 1, 1, 1, 1]
115 3 [100, 10, 5]
116 4 [100, 10, 5, 1]
117 5 [100, 10, 5, 1, 1]
118 6 [100, 10, 5, 1, 1, 1]
119 7 [100, 10, 5, 1, 1, 1, 1]
120 2 [100, 20]```

This Python script can be written much simpler if you don't want to print out the currency composition. I, personally, like seeing it, but the examples in my algorithms classes often call for just knowing the minimum number of bills. In that case, one can re-write this Python script as a simple function.

```# USD - \$1, \$5, \$10, etc.
currency = [1, 5, 10, 20, 50, 100]

def minimum_bills_to_make_change(amount):

# initialize arrays for \$0
minimum_number_of_currency = [10000]*(amount+1)
minimum_number_of_currency[0] = 0

for i in xrange(1, amount + 1):
for j in currency:
if i - j > -1:
minimum_number_of_currency[i] =\
min(minimum_number_of_currency[i], minimum_number_of_currency[i - j] + 1)

return minimum_number_of_currency[amount]```

I can now run a script to find the minimum amount of change for \$120.

```print minimum_bills_to_make_change(120)

2```

If you are learning Dynamic Programming from your computer science and algorithms courses like me, I hope you find this article useful.

I hope to see you on Twitter. I am KoderDojo.

Best Wishes!

Posted by David Hayden
David Hayden is a professional Microsoft web developer. He mentors and tutors computer science students in C, C++, Java, and Python. In addition to writing computer science and programming tutorials at Koder Dojo, he also writes tutorials on C#, ASP.NET Core, and Azure as well as tutorials on Orchard Core.