# Returns true if there exists a subsequence of `A[0…n]` with the given sum
def subsetSum(A, n, k, lookup):
# return true if the sum becomes 0 (subset found)
if k == 0:
return True
# base case: no items left, or sum becomes negative
if n < 0 or k < 0:
return False
# construct a unique key from dynamic elements of the input
key = (n, k)
# if the subproblem is seen for the first time, solve it and
# store its result in a dictionary
if key not in lookup:
# Case 1. Include the current item `A[n]` in the subset and recur
# for the remaining items `n-1` with the decreased total `k-A[n]`
include = subsetSum(A, n - 1, k - A[n], lookup)
# Case 2. Exclude the current item `A[n]` from the subset and recur for
# the remaining items `n-1`
exclude = subsetSum(A, n - 1, k, lookup)
# assign true if we get subset by including or excluding the current item
lookup[key] = include or exclude
# return solution to the current subproblem
return lookup[key]
if __name__ == '__main__':
# Input: a set of items and a sum
A = [7, 3, 2, 5, 8]
k = 14
# create a dictionary to store solutions to subproblems
lookup = {}
if subsetSum(A, len(A) - 1, k, lookup):
print('Subsequence with the given sum exists')
else:
print('Subsequence with the given sum does not exist')
據說這個演算法的復雜度是 O(n * sum)，但我不明白如何或為什么；有人能幫我嗎？可能是冗長的解釋或遞回關系，什么都好
uj5u.com熱心網友回復：
我能給出的最簡單的解釋是意識到當lookup[(n, k)]有一個值時，它是 True 或 False 并指示A[:n 1]總和的某個子集是否為k。
想象一個簡單的演算法，它只是逐行填充查找的所有元素。
lookup[(0, i)]（對于 0 ≤ i≤ total）只有兩個元素為真，i = A[0]和i = 0，所有其他元素為假。
lookup[(1, i)]（為0≤ i≤ total）如果為真lookup[(0, i)]是真還是i ≥ A[1]和lookup[(0, i - A[1])為真。我可以i通過使用A[i]或不使用來達到總和，而且我已經計算了這兩個。
...
lookup[(r, i)]（0≤ i≤ total），如果是真的lookup[(r - 1, i)]是真還是i ≥ A[r]和lookup[(r - 1, i - A[r])為真。
在此表中這樣填寫，很明顯，我們完全可以填補行查找表0 ≤ row < len(A)中的時間len(A) * total，因為在直線中的每個元素填充。我們的最終答案只是檢查(len(A) - 1, sum)表中是否為True。
您的程式正在做完全相同的事情，但是根據需要計算條目的值lookup。
uj5u.com熱心網友回復：
抱歉提交了兩個答案。我想我想出了一個稍微簡單的解釋。
將您的代碼想象成將三行代碼if key not in lookup:放入一個單獨的函式中calculateLookup(A, n, k, lookup)。我會打電話到“呼叫費用calculateLookup的n和k為特定值n，并k要在呼叫花費的總時間calculateLookup(A, n, k, loopup)，但不包括任何遞回呼叫calculateLookup。
關鍵見解是，如上所定義，呼叫的費用calculateLookup()對于任何n和k是O（1）。由于我們在成本中排除了遞回呼叫，并且沒有 for 回圈，因此成本calculateLookup是僅執行一些測驗的成本。
整個演算法做固定的作業量，呼叫calculateLookup，然后做少量的作業。因此，在我們的代碼中花費的時間與詢問我們呼叫多少次相同calculateLookup？
現在我們回到之前的答案。由于查找表的原因，每次呼叫 時calculateLookup都會使用不同的 值(n, k)。我們也知道，我們檢查的范圍n和k每次呼叫之前calculateLookup那么1 ≤ k ≤ sum和0 ≤ n ≤ len(A)。所以calculateLookup在大多數(len(A) * sum)時候被呼叫。
一般來說，對于這些使用記憶/快取的演算法，最簡單的做法是分別計算然后求和：
- 假設您需要的所有值都被快取，事情需要多長時間。
- 填充快取需要多長時間。
您提出的演算法只是填充lookup快取。它以一種不尋常的順序進行操作，并沒有填充表中的每個條目，但這就是它所做的全部。
代碼會稍微快一點
lookup[key] = subsetSum(A, n - 1, k - A[n], lookup) or subsetSum(A, n - 1, k, lookup)
在最壞的情況下不會改變代碼的 O()，但可以避免一些不必要的計算。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/375112.html
上一篇：如何將此方法轉換為遞回？