Python挑戰

Question

我正在做硬幣更換問題。我已經完成了這個問題，它打印出我需要多少硬幣來儘可能減少變化，但是如何更改我的程序以便它還能打印這些硬幣？

下面是一個簡單的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) 

Answer 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。您可以將第二個發佈代碼與第一個代碼結合起來，添加一個列表作爲參數來存儲更改並使用相同的遞歸設計。

Answer 2

你的第一個代碼將適用於一些變化。函數可以返回一個列表，甚至可以返回（count，[coins]）元組。您可能還想排序V.