給定一個排序的整數串列，總是包含 1。使用最小數量的元素求和到目標值的目標值。所有數字都可以使用多個。
e.x. {1,9,10} Target = 18, solution is 2 elements (9 twice).
{1,3,5,7} Target = 15, solution is 3 elements (7,7,1 or 5,5,5)
我知道我們應該檢查我們是否使用了最大數量的元素來填充目標值，但是我對如何正確計算使用的元素數量感到困惑，一旦我們有正確的遞回回傳。
def main():
sections = list(map(int,input().split(" ")))
t = int(input())
print((subset_sum(sections,len(sections)-1,t)), "elements minimum")
def subset_sum(X, i, t):
count = 0
if t == 0:
return 1
if t < 0 or abs(i) == len(X):
return 0
for z in range(0,t//X[i]):
count = subset_sum(X,i-1,t-(z*X[i]))
return count
if __name__ == "__main__":
main()
我的基本情況不正確嗎？既然我想要不正確的情況下回傳 1 的最小值嗎？還是我呼叫遞回時出錯了？
uj5u.com熱心網友回復：
我認為代碼試圖解決與標題中描述的問題不同的問題。您似乎正在計算t使用 中的面額更改金額的不同方法的數量X。這是執行此操作的代碼版本：
def subset_sum(X, i, t):
count = 0
if t == 0:
return 1
if t < 0 or i < 0:
return 0
for z in range(0,t//X[i] 1):
count = subset_sum(X,i-1,t-(z*X[i]))
return count
subset_sum([5, 2, 1], 2, 30) # 58 ways to make change
# same as the following Mathematica code:
# Length@IntegerPartitions[30, All, {1, 2, 5}]
為了找到達到 amount 所需的最小硬幣數量t，您需要修改您的歸納步驟。t您需要取最小值，而不是添加較小的值：
from functools import lru_cache
def coin_change(denominations, target):
'Return minimum number of coins with given denominations to make a target sum'
@lru_cache(None)
def f(target):
if target == 0:
return 0
elif target < 0:
return float("inf")
return min(f(target - d) for d in denominations) 1
return f(target)
coin_change([1, 2, 5], 30) # minimum number of coins is 6
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/425212.html
上一篇：快取和資料庫一致性問題