給定正整數的集合,我想要那些總和是超過閾值的最小和的那些整數的子集。其中總和是特定閾值上的最小和的子集
回答
您的問題是Subset Sum Problem上的變化,並且是NP-complete。
爲了弄明白爲什麼,我們假設你有一個算法可以解決你的問題,並且它會用sum來產生答案。然後,你已經證明,不存在等於s - 1的整數子集,即你有子集求和問題的解決方案。
如果性能不是問題,那麼您可以列舉所有可能的集合。如果性能問題,您可以嘗試在維基百科頁面上查看如何優化這類算法的想法,例如使用動態編程。該頁面上的算法實際上應該像子集求和問題一樣有效地解決您的問題。
只有在子集不連續時才爲真(即,您可以將項目編號3,12和15選入子集) – 2010-02-25 22:21:31
「最小和」:有一個經典的「最大金額」的問題,以及在此描述:http://wordaligned.org/articles/the-maximum-subsequence-problem
這只是一個微小的變化具有「超過閾值」的條件 - 只是一個額外如果您的循環語句。
我不尋找連續的子序列 – 2010-02-26 14:51:05
我有同樣的問題!如果所有N個整數都是正數並且以常數C爲界,那麼就有一個解決方案,其時間和空間要求爲O(NC)。
Pisinger發現了一個線性時間動態規劃算法,以找到閾值下的最大值,這就像問題的逆向。因此,如果您從整數總和中減去所需的閾值,則可以使用Pisinger算法的這個新閾值來找到所需數字中的所有數字。
根據問題整數的大小,這可能會也可能不可行。
Pisinger的論文: http://www.diku.dk/~pisinger/95-6.ps
- 1. MongoDB與總和和最小閾值的聚合
- 2. 數組中具有最小總和的索引集的特定子集
- 3. 最大的二維子集和總和
- 4. 總和的平均值減最小值
- 5. 尋找所有可能子集的最大和最小差異的總和
- 6. 子集總和爲負值
- 7. 找到總和爲特定值的所有子集。遞歸還是DP?
- 8. 子集合中的總和
- 9. 小於給定值的最大子集合和
- 10. 最小/最大 「總和」 的
- 11. 最大和最小總和
- 12. SQL中特定值的總和
- 13. 最小化組,其中族元素的總和低於一定值
- 14. 返回行,其中字段小於給定值的總和
- 15. 箱子的最小和最大值?
- 16. 找到其總和大於給定整數的最小整數集合
- 17. 使用Java Streams確定流的子集是否超過閾值
- 18. 最小的成本總和
- 19. 在數據子集的不同變量中查找最小值和最大值
- 20. 如何計算最小值,最大值,總和,和AVG
- 21. 特徵縮放/歸一化中的最小值和最大值?
- 22. 特定鍵字典的總和值C#
- 23. numpy.linalg.cond是否返回最大和最小特徵值的比率?
- 24. 找到最大值和最小值與AWK在特定範圍
- 25. 中的std ::最大值和最小值
- 26. 行是3個最新值的總和
- 27. 找到總和到給定值的最小素數
- 28. 打印所有子集是總結到特定值
- 29. 如何將一個集合劃分爲K個子集,這樣子集中元素的總和最小?
- 30. 找到最大值和最小值元素高於閾值在容器
連續的子集或不? – 2010-02-25 22:21:02
該子集不必連續 – 2010-02-25 22:44:20