user1681664 - 5 months ago 13

Python Question

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`

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.

Source (Stackoverflow)

Comments