我正在做硬币找零的问题。我已经解决了这个问题,因为它打印出我需要多少硬币才能进行尽可能少的找零,但是我如何更改我的程序以便它也打印这些硬币?
这是一个示例I/O
:
输入:coin_change(48, [1, 5, 10, 25, 50])
输出:[6, [25, 10, 10, 1, 1, 1]]
目前我的代码仅返回6
。
顺便说一句,这必须仅通过递归来完成。不允许循环
代码:
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)
最佳答案
程序的不同版本:
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])
输出:
(6, [25, 10, 10, 1, 1, 1])
(3, [25, 3, 2])
PS:如果您愿意,我会添加解释。
关于Python 硬币变化如此接近,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12535513/