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.

• RomanPerekhrest: post a testable changemakings list values
• Segitsetek: from 1 to 10^7 like [1,18,35,4587425,9400]
• RomanPerekhrest: Can you clarify what does "minimum change" (as resulting digit) conceptually mean? Please provide a more extended description
• Segitsetek: Yes i miss wrote it. I meant coin.

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)