user1681664 user1681664 - 6 months ago 35
Python Question

Python Coin change SO CLOSE

I am doing the coin-change problem. I have finished the problem in that it prints out how many coins I need to make the least amount of change possible, but how do I change my program so that it also prints those coins??

Here is a sample

I/O
:

input:
coin_change(48, [1, 5, 10, 25, 50])


output:
[6, [25, 10, 10, 1, 1, 1]]


Currently my code only returns the
6
.

by the way, this must be done with recursion only. no loops are allowed

Code:

def change(C, V):
def min_coins(i, aC):
if aC == 0:
return 0
elif i == -1 or aC < 0:
return float('inf')
else:
return min(min_coins(i-1, aC), 1 + min_coins(i, aC-V[i]))
return min_coins(len(V)-1, C)

Answer

A different version of your program:

def change(C, V, res=None):
    res = [] if res is None else res
    if len(V) == 0:
        return len(res), res
    maxx = max(V)
    V.remove(maxx)
    ans = C//maxx
    if ans == 0 and maxx < C :
        res += [maxx] * ans
        return len(res), res
    else:
        res += [maxx] * ans
        return  change(C % maxx, V, res)

print change(48,[1, 5, 10, 25, 50])
print change(30,[25, 10, 2, 3, 1])

output:

(6, [25, 10, 10, 1, 1, 1])
(3, [25, 3, 2])

PS: I'll add an explanation if you want.