子集的總和是一個龐大的浮點數

Question

我想解決子集總和問題（https://en.wikipedia.org/wiki/Subset_sum_problem或https://www.cs.cmu.edu/~ckingsf/class/02713-s13/lectures/lec15-subsetsum.pdf）。

但是，我有一些特殊的條件。集合S包括千至10000巨大浮點數（約10^8），目標和W是一個也非常巨大（約10^9）浮動。

現在我想獲得一個子集，其中元素的總和儘可能接近W.我想用動態規劃解決它。但是存儲中等結果的表的大小太大而不能被接受。同時，內循環（對於i = 1到W）也是不可接受的。

是否有任何有效的算法來解決這種子集問題？

Answer 1

重要的是要注意的是，大量的做很少在這種情況下，雙精度的極限大約是10^310（給予或採取大小的幾個訂單）是很重要的。更大的問題是有2^n個子集，所以任何大於30的子集都太大了。在你鏈接的維基百科頁面的末尾，有一個多項式時間近似值，這可能值得更多關注。

另外，dp解決方案需要數量的固定值。考慮到你正在考慮浮點精度，這是不可行的。