子集的总和是一个庞大的浮点数

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解决方案需要数量的固定值。考虑到你正在考虑浮点精度，这是不可行的。