給定n個整數的列表，找到大於X的最小子集總和

Question

給定數組形式的未分類整數集合，找到大於或等於常量整數x的最小子集總和。

如： - 我們集{4 5 8 10 10}和x=15 所以最接近最小的子集總和x和>=x is {5 10}

我只能想到一個天真的算法，其中列出了集合的所有子集和檢查，如果子集的總和並且最小或不是，但其指數算法和列出所有子集需要O（2^N）。我可以使用動態規劃在多項式時間內解決它嗎？

Answer 1

如果所有的數字之和爲S，和你的目標數量爲X，你可以改寫這樣的問題：你可以選擇小於或等於S-X數字的最大子集？

而且你有一個特殊情況下的knapsack problem，其中權重和價值是相等的。

這是一個壞消息，因爲這意味着你的問題是NP難度，但是在好處上你可以使用KP（仍然不是多項式）的動態編程解決方案。或者你可以嘗試KP的多項式逼近，如果這對你來說足夠好。