數組中具有最小總和的索引集的特定子集

您有2個數組a和b，每個數組包含n個數字。你有一個數字k。數組中具有最小總和的索引集的特定子集

[N] =索引設置爲1 ...... n

我們想找到的子集S [n]的，使得元件的被S中一個索引的總和至少爲K，並且總和在S中由S索引的元素的數量儘可能小。

我無法找到甚至多項式時間算法。我會很感激有關如何解決這個問題的任何想法。

2012-07-31 user36338

這是功課嗎？你目前有什麼方法？子集S不一定是連續的元素，對嗎？ – hatchet 2012-07-31 16:41:23

以下類似的問題可能會給你一些想法：http://stackoverflow.com/questions/8099334/maximum-subset-sum-with-two-arrays http://stackoverflow.com/questions/443712/algorithm-to-找到子集中的兩個整數集合，其和數匹配/ 443950＃443950 – hatchet 2012-07-31 16:50:38

這不是家庭作業。我正在讀一個關於向玩家分配資源的問題，在特殊情況下降低到這個水平。我現在看到這是NP完全的。揹包可以在多項式時間內解決到任何精度，我們也可以通過在目標值上進行二分搜索來減少揹包。所以，我想這也可以在多項式時間內解決任何準確性，但我必須驗證這一點。 – user36338 2012-08-01 08:09:58

該問題的一般解決方案是NP完全的，因爲它包含揹包問題。但是，與揹包問題一樣，您可以使用動態規劃以建設性的方式（在「多項式時間」中）解決它。

要看到這一點：給定一個揹包問題，揹包大小T和對象大小c[i]，在你的問題，使得a[i]==b[i]==c[i]和k == sum(c[i]) - T描述構成一個問題。

然後，解決揹包問題是一組指標在S不：

sum(c[i] *not* indexed by S) == sum(c[i]) - sum(a[i] indexed by S) 

T == sum(c[i]) - k

注意S滿足揹包約束sum(c[i] *not* indexed by S) <= T當且僅當問題約束sum(a[i] indexed by S) >= k成立。

sum(c[i] *not* indexed by S) == sum(c[i]) - sum(b[i] indexed by S)

自向提出問題的解決方案最小化sum(b[i] indexed by S)超過有效S，sum(c[i] *not* indexed by S)被最大化超過有效S，並且是揹包問題的最佳解決方案。

來源

2012-07-31 19:29:05 comingstorm

你對至少多項式感興趣嗎？容易有指數迭代所有掩碼的設置和檢查兩個條件（sum> = k並比較我們之前總結的b和現在）

來源

2012-07-31 17:55:38

數組中具有最小總和的索引集的特定子集

回答

相關問題