Money change/minimum coin algorithm

Question

How can I speed up this code?

coin=[50000, 20000, 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
def matrix(coins, kerdes): # it create a metrix
    tabla = [[0 for m in range(kerdes + 1)] for m in range(len(coins) + 1)]

    for i in range(kerdes + 1):
        tabla[0][i] = i
    return tabla

def change_making(coin, change):
    table = matrix(coin, change)
    for c in range(1, len(coin) + 1):
        for r in range(1, change + 1):

            if coin[c - 1] == r:
                table[c][r] = 1

            elif coin[c - 1]> r:
                table[c][r] = table[c-1][r]

            else:
                table[c][r] = min(table[c - 1][r], 1 + table[c][r - coin[c - 1]])

    return table[-1][-1] #return the minimum coin what we need to make the change

newcoin=int(input()) # ask the new coin
coin.append(newcoin) #add to the coin list
coin.sort(reverse=True) #sort the list to get the biggest coin to first

changemakings=[int(x) for x in input().split()] # order the 'orders' to list for easier work with it
for changes in changemakings:

    print(change_making(coin, changes))

This is my code it calculate the minimum coin, with possible to give new coin which will result a non canonical change system.

Answer 1

I ran a few examples through the code and I have made the following assumptions:

• the code calculates the minimum amount of coins needed to produce the user's input

• the user can enter in a custom coin and it will use that as part of its calculations

Instead of using a matrix, I just found the highest coin which can be used to make change, then subtracted it from the total user inputted amount, and repeated it until there was no change left.

coins = [50000, 20000, 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1]

coinToAdd = int(input("Enter in coin to add to coins:"))
userMoney = int(input("Enter in coin to calculate change:"))
coins.append(coinToAdd)
coins.sort(reverse=True)
totalCoins = 0
while [j for j in coins if userMoney >= j]:
  userMoney = userMoney - [j for j in coins if userMoney >= j][0]
  totalCoins = totalCoins + 1

print(totalCoins)