其中總和是特定閾值上的最小和的子集

給定正整數的集合，我想要那些總和是超過閾值的最小和的那些整數的子集。其中總和是特定閾值上的最小和的子集

2010-02-25 Adam Tegen

連續的子集或不？ – 2010-02-25 22:21:02

該子集不必連續 – 2010-02-25 22:44:20

您的問題是Subset Sum Problem上的變化，並且是NP-complete。

爲了弄明白爲什麼，我們假設你有一個算法可以解決你的問題，並且它會用sum來產生答案。然後，你已經證明，不存在等於s - 1的整數子集，即你有子集求和問題的解決方案。

如果性能不是問題，那麼您可以列舉所有可能的集合。如果性能問題，您可以嘗試在維基百科頁面上查看如何優化這類算法的想法，例如使用動態編程。該頁面上的算法實際上應該像子集求和問題一樣有效地解決您的問題。

2010-02-25 22:17:27

只有在子集不連續時才爲真（即，您可以將項目編號3,12和15選入子集） – 2010-02-25 22:21:31

「最小和」：有一個經典的「最大金額」的問題，以及在此描述：http://wordaligned.org/articles/the-maximum-subsequence-problem

這只是一個微小的變化具有「超過閾值」的條件 - 只是一個額外如果您的循環語句。

2010-02-25 22:20:22

我不尋找連續的子序列 – 2010-02-26 14:51:05

我有同樣的問題！如果所有N個整數都是正數並且以常數C爲界，那麼就有一個解決方案，其時間和空間要求爲O（NC）。

Pisinger發現了一個線性時間動態規劃算法，以找到閾值下的最大值，這就像問題的逆向。因此，如果您從整數總和中減去所需的閾值，則可以使用Pisinger算法的這個新閾值來找到所需數字中的所有數字。

根據問題整數的大小，這可能會也可能不可行。

2013-06-20 20:22:31 Athena

回答