用於查找子數組元素的總和是否可以生成所需總和的算法

我想實現一個算法，該算法將告訴您所需的總和是否可以從給定的數組元素中生成。用於查找子數組元素的總和是否可以生成所需總和的算法

我已經用此程序

def check_payment(arr, requested_money): 
arr.sort() 
arr.reverse() 
sum = 0 
for item in arr: 
    sum += item 
    if sum == requested_money: 
     return True 
    elif sum > requested_money: 
     sum -= item 

return False

我不知道它在哪裏得到錯誤的走了過來。一些測試案例失敗。你能否給我提供一個場景，哪裏會失敗。

來源

2017-08-14 Diamond Mohanty

*我不知道它在哪裏出錯* - 實際上到處都是。只有在檢查的最後一個元素溢出時纔會回溯，但不關心以前的元素。這種類型的問題自然是用遞歸解決的。 –

可能的方法：http://www.geeksforgeeks.org/write-ac-program-that-given-a-set-a-of-n-numbers-and-another-number-x-determines-whether-or-並非存在 - 兩個元素在S - 誰的總和是 - 完全-X/ 存檔：https：//web.archive.org/web/20151221002246/http：//www.geeksforgeeks。組織/寫-AC-程序 - 即賦予-A-設置-A-的正號和 - 另一數-X-確定-是否有或未存在-存在二個元素，IN- s-which-sum-is-exactly-x/ –

據我瞭解你的問題定義，這是一個稱爲https://en.wikipedia.org/wiki/Subset_sum_problem的NP-Complete問題。所以，如果你的數據集很大，這個問題就不存在多項式時間（即短時間）算法。你的數據的大小是多少？ – msalperen

情景 - 當你的代碼沒有

運行你的代碼，此陣： -

[10,16,25] - original array say arr 
arr.sort() - [10,16,25] 
arr.reverse() - [25,16,10]

現在申請，對循環和搜索requested_money 26

希望這有助於你。

來源

2017-08-14 18:52:54

請查看他問題的最後一行 - 我不知道它出錯的地方。一些測試案例失敗。你能否給我提供一個場景，哪裏會失敗。 –

是的，我已經看到它並刪除了我的評論，對不起 –

沒問題Eugene –

用於查找子數組元素的總和是否可以生成所需總和的算法

回答

相關問題