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 Koder Dojo

Hi! I am a freelance ASP.NET C# MVC Developer learning Python. I am taking several online computer science and algorithms courses. My algorithms courses are teaching me a lot about greedy algorithms, divide-and-conquer algorithms, and dynamic programming algorithms to solve classic problems. I am writing about my adventures in this blog to help reinforce my learning as well as help others learn the topics as well. I hope you find my examples useful. Most of them are based on actual programming assignments. You can find me on twitter as Koder Dojo.

Related Posts: