Python dynamic program for minimum change with arbitrary currency values

In my videos:

Recursion 9 | Min Coins - Dynamic Programming 1 (12:01)
Recursion 10 | Min Coin - Dynamic Programming 2 (10:17)

that work along with the Miller ebook:
Problem Solving with Algorithms and Data Structures using Python

code is presented to solve the problem of choosing the minimum number of coins to to make change for an amount utilizing dynamic programming. These videos walk you through how to solve this problem in different ways including handling adding a new 21 cent coin to the normal US mix of pennies, nickels, dimes, and quarters.

A comment from a youtube viewer asked if the code could solve for coin values that sometimes did not have a solution.

I have modified the original code and here is that solution in python for those interested. The dynamic programming technique builds a list all solutions up to the one asked for in the dpMakeChange method and stores those solutions in the lists coinCount and coinsUsed.

Here is the new code:



# modification to dynamic programming Miller solution:
#   http://interactivepython.org/runestone/static/pythonds/Recursion/DynamicProgramming.html
# in the case of arbitrary coin currency amounts that there is not always a solution

def dpMakeChange(coinValueList, change, minCoins, coinsUsed):
    smallestCoin = coinValueList[0]
    minCoins[smallestCoin] = 1
    coinsUsed[smallestCoin] = smallestCoin
    for cents in range(smallestCoin + 1, change + 1):
        coinCount = cents + 1  # pick biggest possible to replace with min
        newCoin = smallestCoin
        for j in [c for c in coinValueList if c <= cents]:
            prevSolution = minCoins[cents - j]  # add this coin to prev solution
            # check if exact coin or prevSolution exist and a new minimum was found
            if j == cents or (prevSolution != 0 and prevSolution + 1 < coinCount):
                coinCount = prevSolution + 1
                newCoin = j
        if coinCount < cents + 1:  # found a solution min
            minCoins[cents] = coinCount
            coinsUsed[cents] = newCoin
    return minCoins[change]

def printCoins(coinsUsed, change):
    coin = change
    if coinsUsed[coin] == 0:
        print(f"no solution for {change}")
        return
    while coin < 0:
        thisCoin = coinsUsed[coin]
        print(thisCoin)
        coin = coin - thisCoin


def main():
    amnt = 63
    clist = [1, 5, 10, 21, 25]  # these are the coins to choose from
    coinsUsed = [0] * (amnt + 1)
    coinCount = [0] * (amnt + 1)

    print("Making change for", amnt, "requires")
    print(dpMakeChange(clist, amnt, coinCount, coinsUsed), "coins")
    print("They are:")
    printCoins(coinsUsed, amnt)
    print("The used list is as follows:")
    print(coinsUsed)
    print(coinCount)


main()