（在你回覆其他SO問題的鏈接或將其作爲副本關閉之前，請仔細閱讀該問題。這與此問題的標準變體不同，並且我搜索了很長時間所以我敢肯定沒有這樣這裏的問題）有特殊情況的子集合
我需要找到如果最小的小號是X的一些子集的總和[I]是> = T（一些目標值，小於全集的總和）。
該集合不是很大（約40個元素），但對於指數回溯解決方案仍然太大。
的數和金額是巨大的（約10^15），因此動態規劃是不行的（可能狀態的數量很大，因此記憶化表將很快耗盡內存）。
由於相同的原因，Pisinger的線性時間算法將不起作用（它是O（nr），其中r是和的上限，在這種情況下這太大）。
是否有一些確定性算法，可以幫助我在這種情況下的大數目，但數量很少？我不想訴諸某種近似算法。
鑑於上述條件，我相信帶有branch & bound的回溯解決方案是獲得確切解決方案的最佳選擇。
這個想法是檢查所有子集，但是可以在算法運行期間修剪一些可能子集的計算樹。
例如，假設您正在尋找S = 10^8，你已經找到了sol=10^8 + 10^7的解決方案，現在，您所檢查的是一些X超集所有子集，並且你發現sum(X) = 10^9。沒有必要繼續檢查任何包含X的子集，您可以跳過它們 - 它們不會使您達到最佳狀態。
我也嘗試並行化解決方案，分支和綁定通常很容易並行化，只需要在一段時間內同步新的最佳解決方案。
正如你所說，這個集合並不是很大（約40）。我認爲複雜度爲O(2^(n/2) n)的經典指數時間算法將符合您的需要http://en.wikipedia.org/wiki/Subset_sum_problem#Exponential_time_algorithm。
我可以簡單介紹一下這裏的方法。將該集合拆分爲兩個相等大小的集合，比如說A和B.並且枚舉子集合，以便生成兩個大小爲2^(n/2)的集合，比如PA和PB。然後，您可以對PA和PB進行排序，然後使用二分查找找到超過T的時間總和O(2^(n/2) n)。