我試圖解決硬幣找零問題。你得到一筆錢（例如 55 美分），并且必須盡可能少地返還硬幣。我的解決方案非常簡單（而且可能效率極低）。我試圖用蠻力做到這一點。首先，我嘗試用硬編碼的固定硬幣來做，效果很好money = 55def findMinCoins(money): nq = int(money/25) nd = int(money/10) nc = int(money/1) smallest = nq + nd + nc for q in range(nq+1): for d in range(nd+1): for c in range(nc+1): if q*25 + d*10 + c == money: if q + d + c < smallest: smallest = q + d + c print(q, d, c) return smallest之后，我嘗試使用諸如 coin = [25, 10, 1] 之類的硬幣數(shù)組來做到這一點，這就是我的問題。coins = [25, 10, 1]def findMinCoins(money, coins): n_coins = [(int(money/coin) for coin in coins)] smallest = sum(n_coins)我不知道我應(yīng)該如何對數(shù)組進行 for 循環(huán)。有人可以幫我找到解決方案嗎？
3 回答
蕪湖不蕪
TA貢獻1796條經(jīng)驗 獲得超7個贊
您可以使用從當(dāng)前貨幣中扣除的每個硬幣進行遞歸調(diào)用，并從調(diào)用的返回值中獲取最小值。如果扣除導(dǎo)致貨幣小于 0，則返回?zé)o窮大，這樣它就不會被認為是可行的：
def findMinCoins(money, coins):
if money < 0:
return float('inf')
return money and min(findMinCoins(money - coin, coins) for coin in coins) + 1
以便：
findMinCoins(55, [25, 10, 1])
返回：
4
然而，上面的遞歸很慢，因為在考慮不同的路徑時，它會以相同的金額進行大量調(diào)用。您可以通過使用 dict 作為緩存來記憶給定金額和硬幣組合的結(jié)果，從而顯著提高性能：
def findMinCoins(money, coins, cache={}):
key = money, tuple(coins)
if key in cache:
return cache[key]
if money < 0:
number = float('inf')
else:
number = money and min(findMinCoins(money - coin, coins) for coin in coins) + 1
cache[key] = number
return number
至尊寶的傳說
TA貢獻1789條經(jīng)驗 獲得超10個贊
從字面上重寫你的for循環(huán)：
>>> money=55
>>> lst=[(q+d+c, [q,d,c]) for q in range(int(money/25)+1) for d in range(int(money/10)+1) for c in range(int(money/1)+1) if q*25 + d*10 + c == money]
>>> lst
[(55, [0, 0, 55]), (46, [0, 1, 45]), (37, [0, 2, 35]), (28, [0, 3, 25]), (19, [0, 4, 15]), (10, [0, 5, 5]), (31, [1, 0, 30]), (22, [1, 1, 20]), (13, [1, 2, 10]), (4, [1, 3, 0]), (7, [2, 0, 5])]
然后找到最合適的：
>>> list(filter(lambda x: x[0]==min(el[0] for el in lst), lst))
[(4, [1, 3, 0])]
- - - - - - -編輯
概括解決方案：
>>> import itertools
>>> money=55
>>> coins=[25,10,1]
>>> lst=[(len(el), el) for num in range(1, money//min(coins)+1) for el in itertools.combinations_with_replacement(coins, num) if sum(el) == money]
>>> lst
[(4, (25, 10, 10, 10)), (7, (25, 25, 1, 1, 1, 1, 1)), (10, (10, 10, 10, 10, 10, 1, 1, 1, 1, 1)), (13, (25, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)), (19, (10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)), (22, (25, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)), (28, (10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)), (31, (25, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)), (37, (10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)), (46, (10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)), (55, (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1))]
>>> list(filter(lambda x: x[0]==min(el[0] for el in lst), lst))
[(4, (25, 10, 10, 10))]
以上內(nèi)容非常籠統(tǒng)，對于您的問題，尤其是您的硬幣中的問題 - 您可能希望通過將潛在硬幣數(shù)量的上限替換為任何其他正整數(shù)1 cent來大大減少計算次數(shù)。money//min(coins)+1
例如：
>>> coins=[1,2,5,25,50]
>>> money=100
>>> lst=[(len(el), el) for num in range(1, 5) for el in itertools.combinations_with_replacement(coins, num) if sum(el) == money]
>>> lst
[(2, (50, 50)), (3, (25, 25, 50)), (4, (25, 25, 25, 25))]
>>> list(filter(lambda x: x[0]==min(el[0] for el in lst), lst))
[(2, (50, 50))]
墨色風(fēng)雨
TA貢獻1853條經(jīng)驗 獲得超6個贊
可能有一種更 Pythonic 的方式來做到這一點，但一般的遞歸方法是這樣做的：
取剩余的金額嘗試對每個硬幣進行遞歸調(diào)用，以減少金額而不會變?yōu)樨摂?shù)。取該集合中最小的結(jié)果
def findMinCoins(money, coins):
if money <= 0:
return 0
results = []
for c in coins:
if money >= c:
results.append(1 + findMinCoins(money-c, coins))
results.sort()
return results[0] #return the smallest result
現(xiàn)在上面唯一的問題是它非常慢，因為它會對先前計算的值進行大量冗余調(diào)用。因此，我們將對其進行修改，以便為每個最終結(jié)果提供一個查找表，并以遞歸方式傳遞。
def findMinCoins(money, coins, lookup):
if money <= 0:
return 0
if money in lookup:
return lookup[money]
results = []
for c in coins:
if money >= c:
results.append(1 + findMinCoins(money-c, coins, lookup))
results.sort()
best = results[0]
lookup[money] = best
return best
測試一些例子：
>>> findMinCoins(95,[25,10,5,1], {})
5
>>> findMinCoins(4,[25,10,5,1], {})
4
>>> findMinCoins(44,[25,10,5,1], {})
7
添加回答
舉報
0/150
提交
取消