我有這個問題：你有一個 [7,9,11] 筆的清單。你有一個功能：
def can_i_buy(x):
您需要檢查是否可以購買確切的數量。
例如，我有 X=23
我可以購買1*9, 2*7
我只需要回傳 True 如果可以，否則回傳 false。
我看到了答案，他們用 3 個 for 回圈蠻力做到了（瘋狂）。
我嘗試了遞回，這很好，但似乎它很長 重復的部分 它并不完全好，因為我不知道在哪里放置 False 陳述句.. 我的退出點是什么。
該代碼有效，但不完全正確。
def can_i_buy(x): # 23
return helper(x, [7,9,11])
def helper(x, lst):
if x == 0:
return True
if x < 0:
return
take_1 = helper(x - lst[0], lst)
if take_1 == True:
return take_1
take_2 = helper(x - lst[1], lst)
if take_2 == True:
return take_2
take_3 = helper(x - lst[2], lst)
if take_3 == True:
return take_3
如何解決？另外，我對這里的退出宣告有何看法？我不知道如何退出它......我應該在哪里放假，以及如何？
編輯：添加列印 輸出
print(can_i_buy(24))
print(can_i_buy(23))
print(can_i_buy(7))
print(can_i_buy(14))
輸出：
None
True
True
True
我應該沒有收到 - 錯誤。但我不知道把 False 陳述句放在哪里......當所有的遞回結束時，我不知道如何放置它。
uj5u.com熱心網友回復：
遞回呼叫應該從 中減去每個價格x，直到x為 0（在這種情況下 return True）或小于 0（在這種情況下 return False）：
def can_i_buy(x, lst):
return not x or x > 0 and any(can_i_buy(x - i, lst) for i in lst)
如果您只想修復代碼，則可以False在所有將回傳的條件都失敗時在函式末尾回傳True：
def helper(x, lst):
if x == 0:
return True
if x > 0:
take_1 = helper(x - lst[0], lst)
if take_1 == True:
return take_1
take_2 = helper(x - lst[1], lst)
if take_2 == True:
return take_2
take_3 = helper(x - lst[2], lst)
if take_3 == True:
return take_3
return False
或者，如果您被允許進行for回圈：
def helper(x, lst):
if x == 0:
return True
if x > 0:
for i in lst:
if helper(x - i, lst):
return True
return False
演示：
我敢打賭，您可以在這里輕松找到不需要的作業，對吧？看看綠點和紅點，如果我們已經計算了具有值的節點的結果5（對于 相同7），我們真的需要稍后再計算嗎？我們可以以某種方式快取之前計算的結果嗎？是的，我們可以通過記憶（你也可以使用@cache裝飾器而不是顯式快取）。
自上而下的記憶
memo = {}
def can_i_buy(alist, target):
if target == 0:
return True
if target < 0:
return False
if target in memo:
return memo[target]
for i in range(len(alist)):
diff = target - alist[i]
memo[diff] = can_i_buy(alist, diff)
if memo[diff]:
return True
return False
print(can_i_buy([11, 9, 7], 23))
print(memo) # {-10: False, -8: False, -6: False, 1: False, -4: False, 3: False, -2: False, 5: False, 12: False, 0: True, 7: True, 14: True}
還有一種方法稱為自下而上。通常，它更難提出，但它更好地顯示了子問題之間的關系。
自下而上
def can_i_buy(target):
dp = [True] [False] * target
for num in range(1, target 1):
for coin in alist:
if num - coin >= 0:
dp[num] = dp[num] or dp[num - coin]
return dp[target]
您也可以使用廣度優先搜索方法，它與自上而下的方法非常相似。
廣度優先
from collections import deque
def can_i_buy(alist, target):
seen = set()
queue = deque([target])
while queue:
t = queue.popleft()
if t == 0:
return True
for val in alist:
diff = t - val
if diff >= 0 and diff not in seen:
queue.append(t - val)
seen.add(diff)
return False
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/507859.html
上一篇：根據第一個ID查詢獲取遞回記錄
下一篇：拋硬幣的總可能結果