algorithm - 总和是一个巨大的 float 的子集总和

Question

我正在尝试解决子集和问题( https://en.wikipedia.org/wiki/Subset_sum_problem 或 https://www.cs.cmu.edu/~ckingsf/class/02713-s13/lectures/lec15-subsetsum.pdf )。

但是，我有一些特殊的条件。集合S由一千到一万个巨大的 float (约10^8)组成，目标和W也是一个非常大(约10^9)的 float .

现在我想得到一个子集，其中元素和与W接近。我想用动态规划来解决它。但是存储中等结果的表的大小太大了，无法接受。同时，内层循环(for i = 1 to W)也是 Not Acceptable 。

有没有什么高效的算法可以解决这类子集问题？

Answer 1

重要的是要注意，在这种情况下，大数字的作用很小，因为 double 的限制约为 10^310(上下 float 几个数量级)。更大的问题是有 2^n 个子集，因此任何大于 30 左右的 n 都太大了。在您链接的维基百科页面的末尾，有一个多项式时间近似值，可能值得深入研究。

此外，dp 解决方案需要固定数量的数字值。考虑到您正在查看浮点精度，这是不可行的。