0

我正在做硬币找零的问题。我已经完成了这个问题，它会打印出我需要多少硬币才能尽可能减少零钱，但是我如何更改我的程序以便它也打印这些硬币？

这是一个示例 I/O：

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

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

input: coin_change(48, [1, 7, 24, 42])

output: [2, [24, 24]]

目前我的代码只返回 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 giveChange(C, V, res = None):
    res=[] if res is None else res
    if len(V)==0:
        return len(res),res
    maxx=max(V)
    print maxx
    V.remove(maxx)
    ans=C//maxx
    if ans==0 and maxx<C :
        print maxx
        res +=[maxx]*ans
        return  len(res),res
    else:
        res += [maxx]*ans
        return  giveChange(C % maxx,V,res)
4

2 回答 2

1

可能不使用 maxx=max(V)

最优解可以包括小硬币，例如48=24+24，它有两个硬币，小于48=25+10+10+1+1+1。在这种情况下，虽然 25>24，但您必须使用更多的小硬币来制作 48。

因此，如果您的输入是 (48, [1, 7, 24, 42])，您将陷入第二种情况并得到 48 = 42+1+1+1+1+1+1。您可以将第二个发布的代码与您的第一个代码结合起来，添加一个列表作为参数来存储更改并使用相同的递归设计。

于 2012-09-22T04:43:16.640 回答
0

您的第一个代码将进行一些更改。一个函数不仅可以返回 count，还可以返回一个列表甚至 (count, [coins]) 元组。您可能还想对 V 进行排序。

于 2012-09-22T05:13:28.350 回答