這是一個偉大的算法問題，但說實話，我不認爲你的實現是正確的，也可能是我不明白你的函數的輸入/輸出，爲此我表示歉意。
繼承人您的實施的修改版本。
def C(i, coins, cdict = None):
if cdict == None:
cdict = {}
if i <= 0:
cdict[i] = 0
return cdict[i]
elif i in cdict:
return cdict[i]
elif i in coins:
cdict[i] = 1
return cdict[i]
else:
min = 0
for cj in coins:
result = C(i - cj, coins)
if result != 0:
if min == 0 or (result + 1) < min:
min = 1 + result
cdict[i] = min
return cdict[i]
這是我在解決類似的問題的嘗試，但這次返回硬幣的列表。我最初開始使用遞歸算法，該算法接受一個金額和一個硬幣列表，如果沒有找到這樣的配置，它可以返回一個列表中最小數量的硬幣列表或None列表。
def get_min_coin_configuration(sum = None, coins = None):
if sum in coins: # if sum in coins, nothing to do but return.
return [sum]
elif max(coins) > sum: # if the largest coin is greater then the sum, there's nothing we can do.
return None
else: # check for each coin, keep track of the minimun configuration, then return it.
min_length = None
min_configuration = None
for coin in coins:
results = get_min_coin_configuration(sum = sum - coin, coins = coins)
if results != None:
if min_length == None or (1 + len(results)) < len(min_configuration):
min_configuration = [coin] + results
min_length = len(min_configuration)
return min_configuration
好吧，現在讓我們看看我們是否可以通過使用動態編程（我稱之爲緩存）來改進它。
def get_min_coin_configuration(sum = None, coins = None, cache = None):
if cache == None: # this is quite crucial if its in the definition its presistent ...
cache = {}
if sum in cache:
return cache[sum]
elif sum in coins: # if sum in coins, nothing to do but return.
cache[sum] = [sum]
return cache[sum]
elif max(coins) > sum: # if the largest coin is greater then the sum, there's nothing we can do.
cache[sum] = None
return cache[sum]
else: # check for each coin, keep track of the minimun configuration, then return it.
min_length = None
min_configuration = None
for coin in coins:
results = get_min_coin_configuration(sum = sum - coin, coins = coins, cache = cache)
if results != None:
if min_length == None or (1 + len(results)) < len(min_configuration):
min_configuration = [coin] + results
min_length = len(min_configuration)
cache[sum] = min_configuration
return cache[sum]
現在讓我們運行一些測試。
assert all([ get_min_coin_configuration(**test[0]) == test[1] for test in
[({'sum':25, 'coins':[1, 5, 10]}, [5, 10, 10]),
({'sum':153, 'coins':[1, 5, 10, 50]}, [1, 1, 1, 50, 50, 50]),
({'sum':100, 'coins':[1, 5, 10, 25]}, [25, 25, 25, 25]),
({'sum':123, 'coins':[5, 10, 25]}, None),
({'sum':100, 'coins':[1,5,25,100]}, [100])] ])
授予此測試不夠健壯，您也可以這樣做。
import random
random_sum = random.randint(10**3, 10**4)
result = get_min_coin_configuration(sum = random_sum, coins = random.sample(range(10**3), 200))
assert sum(result) == random_sum
它的可能是沒有這樣的硬幣組合等於我們的random_sum，但我相信它不太可能...
我確定有更好的實現，我試圖強調可讀性而不是性能。 祝你好運。
更新 以前的代碼有一個小錯誤的假設，以檢查分硬幣並非最大，重新寫了算法PEP8合規性和返回[]當沒有組合可以發現，而不是None。
def get_min_coin_configuration(total_sum, coins, cache=None): # shadowing python built-ins is frowned upon.
# assert(all(c > 0 for c in coins)) Assuming all coins are > 0
if cache is None: # initialize cache.
cache = {}
if total_sum in cache: # check cache, for previously discovered solution.
return cache[total_sum]
elif total_sum in coins: # check if total_sum is one of the coins.
cache[total_sum] = [total_sum]
return [total_sum]
elif min(coins) > total_sum: # check feasibility, if min(coins) > total_sum
cache[total_sum] = [] # no combination of coins will yield solution as per our assumption (all +).
return []
else:
min_configuration = [] # default solution if none found.
for coin in coins: # iterate over all coins, check which one will yield the smallest combination.
results = get_min_coin_configuration(total_sum - coin, coins, cache=cache) # recursively search.
if results and (not min_configuration or (1 + len(results)) < len(min_configuration)): # check if better.
min_configuration = [coin] + results
cache[total_sum] = min_configuration # save this solution, for future calculations.
return cache[total_sum]
assert all([ get_min_coin_configuration(**test[0]) == test[1] for test in
[({'total_sum':25, 'coins':[1, 5, 10]}, [5, 10, 10]),
({'total_sum':153, 'coins':[1, 5, 10, 50]}, [1, 1, 1, 50, 50, 50]),
({'total_sum':100, 'coins':[1, 5, 10, 25]}, [25, 25, 25, 25]),
({'total_sum':123, 'coins':[5, 10, 25]}, []),
({'total_sum':100, 'coins':[1,5,25,100]}, [100])] ])
如果我<0，你真的想返回0嗎？如果你要求你的程序使20美分出標準的美國硬幣，你的程序將返回1，因爲20 - 25 = -5，所以在遞歸調用程序將返回0，所以你的遞歸調用的最小值將是1，這似乎不正確（除非我誤解了這個問題）。另外，是cdict某種類型的memoizer？ – user1413793
yea cdict會記住以前的解決方案。例如cdict [10]將包含10個金額所需的最少數量的硬幣。我已經意識到，如果我
user5198
是的，一旦你返回0，min將它作爲最小配置選取。 ..簡單地檢查0，因爲我沒有爲None。 –