從給定的面額列表和目標值創建更改

-5

def changeMaking(changeList, target): 
     changeLength = len(changeList) 
     F = [0]*changeLength 


     for i in range(1,target): 
     minimum = 99999 
     j = 1 
     for j in range(1, changeLength): 
      if changeList[j] <= i: 
       if 1+F[i-changeList[j] < minimum: 
         minimum = 1 + F[i-changeList[j]] 
         coin = j 
     return F[i] = minimum 


def main(): 

    changeList = [1, 5, 10, 15, 25] #coin denominations 
    target = 150 

    result = changeMaking(changeList, target) 

    print(result) 
main()

我正在嘗試進行更改，但我無法弄清楚如何使此算法工作。問題應該是顯而易見的......它不起作用。該算法試圖做的是找到所需的最低數量的硬幣來找到目標數量。從給定的面額列表和目標值創建更改

來源

2012-04-11 Jordan Hochstetler

您還沒有告訴我們您的問題或問了一個問題，「請調試此代碼」對未來的其他人沒有幫助。 – agf 2012-04-11 19:12:04

如果我知道是什麼問題，我不需要在這裏發佈...我會嗎？ – 2012-04-11 19:16:31

是的，但「不起作用」並不顯示任何努力來確定具體問題。 _它不起作用？嘗試量化錯誤。 – agf 2012-04-11 19:17:36

這對你來說如何？

def changeMaking(list, amount, check=False): 
    list = reversed(sorted(list)) 
    result = [] 
    changeCount = 0 
    for coin in list: 
     count = 0 
     while changeCount + coin <= amount: 
      changeCount = changeCount + coin 
      count = count + 1 

     if count > 0: 
      result.append([coin, count]) 
    if not check or changeCount == amount: 
     return result 
    else: 
     return False

你沒有給我們提供太多的信息，所以我想你會希望它儘可能地返回。

它的工作原理是這樣

change = changeMaking(coins, amount)

例如

change = changeMaking([1, 2, 5, 10, 20, 50, 100], 56)

它返回

[[50, 1], [5, 1], [1, 1]]

它還接受第三個參數，它爲真時，函數檢查變化是可能的（如果你的硬幣列表中有1個，這應該總是成立的......）

來源

2012-04-11 19:37:25 Nathaniel

'changeMaking（[1,10,25,50,100]，30）'給出非最佳結果。請參閱http://oucsace.cs.ohiou.edu/~razvan/courses/cs404/lecture19.pdf的第3頁。 – 2012-04-11 19:41:07

@StevenRumbalski經典編程年1小時問題:( – George 2012-04-11 19:50:58

謝謝你，雖然我看不到我的功能的直接補丁。 – Nathaniel 2012-04-11 19:53:56

從給定的面額列表和目標值創建更改

回答

相關問題