查找哪個硬幣組成總數的最小值

Question

給定硬幣數組[1, 3, 7, 12]和總數（29）查找需要補償金額的最小數量（正確答案是4）。

我的代碼正確地找到了最小數量的硬幣，但沒有使用哪個硬幣來獲得最小值。我試着用字典來做，但我得到了很高的數字。

def changeSlow(coinValueList, total, coinDict): 
    if total == 0: 
     return 0 

    res = sys.maxint 

    for i in range(len(coinValueList)): 
     if coinValueList[i] <= total: 
      sub_res = changeSlow(coinValueList, total-coinValueList[i], coinDict) 

      if sub_res != sys.maxint and sub_res + 1 < res: 
       res = sub_res + 1 

     if coinValueList[i] not in coinDict: 
      coinDict[coinValueList[i]] = 0 
     else: 
      coinDict[coinValueList[i]] += 1 

    return res 

coins = [1, 3, 7, 12] 
coinDict = {} 
print(changeSlow(coins, 29, coinDict)) >> gives 4 correctly 
print(coinDict) >> gives {1: 190992, 3: 190992: 7: 190992, 12:190992} 

我得到的輸出是不正確的，不知道爲什麼我收到一個錯誤：

>> 4 
>> {1: 190992, 3: 190992: 7: 190992, 12:190992} 

任何人都可以給我什麼，我做錯了什麼祕訣嗎？我應該提到，我必須使用某種遞歸來實現此解決方案。

Answer 1

5實際上是不正確的。正確答案是4（12,7,7,3）。你得到大量數據的原因是因爲你在整個函數中使用了相同的字典引用，因此每次遞歸調用都會增加相同的字典。您希望每次遞歸調用都使用並增加自己的字典。

由於Untitled123提到的貪婪並不一定是正確的，因爲它錯過了選擇最高硬幣不一定是正確答案的情況（這是這種情況，因爲選擇12兩次而不是選擇12一次，然後7兩次讓你回答5，而不是4）。

這裏是我的是非貪婪的解決方案：

# Not really faster, but it avoids your huge numbers issue 
def changeFast(coinValueList, total, numCoins, coinDict): 

    # Base Case: we've reached the money total we want 
    if total == 0: 
     return (numCoins, coinDict) 

    bestCoins = -1 
    bestDict = {} 

    for i in range(len(coinValueList)): 

     # You need to pass a copy of the dictionary to the 
     # recursive calls. Otherwise each recursive call will 
     # update the same dictionary! 
     dictCopy = {} 
     for coin in coinValueList: 
      dictCopy[coin] = coinDict[coin] 

     coin = coinValueList[i] 

     if coin <= total: 

      # Increment the corresponding coin slot in the dictionary 
      dictCopy[coin] += 1 
      (subCoins, subDict) = changeFast(coinValueList, total - coin, numCoins + 1, dictCopy) 

      # Update our best results so far 
      if bestCoins == -1 or subCoins < bestCoins: 
       bestCoins = subCoins 
       bestDict = subDict 

    return (bestCoins, bestDict) 


coins = [1, 3, 7, 12] 

baseDict = {} 
for coin in coins: 
    baseDict[coin] = 0 

print(changeFast(coins, 29, 0, baseDict)) 
# Returns (4, {1: 0, 3: 1, 7: 2, 12: 1}) as expected 

Answer 2

這是我用遞歸的解決方案。這是做這件事的好方法，但我相信還有更好的辦法。

def changeSlow(coinValueList, total, coinsDict): 
    if total == 0: 
     return 0 
    if total >= max(coinValueList): 
     total -= max(coinValueList) 
     coinsDict[str(max(coinValueList))] += 1 
    else: 
     coinValueList.pop() 
     return changeSlow(coinValueList, total, coinsDict) 
    print(coinsDict) 
    return 1 + changeSlow(coinValueList, total, coinsDict) 



coins = [1, 3, 7, 12] 
coinsDict = {'1': 0, '3': 0, '7': 0, '12': 0} 
print(changeSlow(coins, 29, coinsDict)) 

的這個輸出是5枚硬幣：

{'3': 0, '7': 0, '1': 0, '12': 1} 
{'3': 0, '7': 0, '1': 0, '12': 2} 
{'3': 1, '7': 0, '1': 0, '12': 2} 
{'3': 1, '7': 0, '1': 1, '12': 2} 
{'3': 1, '7': 0, '1': 2, '12': 2} 
5 

讓我知道如果你需要任何澄清。希望這可以幫助。

Answer 3

這確實應該用DP來完成，但是你的函數名稱表明你已經認識到了這一點。對於[1,7,11]和14美分的情況，貪婪解決方案失敗，所以你不能一般使用它。在特殊情況下，你只能使用貪婪的解決方案，普通的[1,5,10,25,50,100]就是貪婪的工作。

下面是一個非常低效的遞歸解決方案。

def changeSlow(coinValueList, total): 
    options=[] 
    for coin in coinValueList: 
    if coin < total: 
     res=changeSlow(coinValueList, total-coin) 
     if res: 
     options.append([coin] + res) 
    elif coin==total: 
     return [coin] 
    if options: 
    return sorted(options, key=lambda x: len(x))[0] 
    return [] 

coins = [1, 3, 7, 12] 
result=changeSlow(coins,29) 
print result, len(result)