具有浮点和目标和或目标和的最近和的子集和问题的多项式\伪多项式算法

Question

我想知道是否存在一个算法来计算带有目标和的排序列表（允许浮点数和重复数）的“所有可能的组合”，如果没有任何组合等于目标总和，则算法返回“all在多项式或伪多项式时间内对目标和的最近和（下界）的可能组合。我检查了Balsub算法“有界权重的背包问题的线性时间算法”以及多项式时间的“子集和的更快的伪多项式时间算法”，但我不确定这些问题在时间复杂度上是否相同。

这是一个例子：

Sorted List: {1.5, 2.25, 3.75, 3.81}
Target = 3.79
Results: {1.5, 2.25}, {3.75} = 3.75

谢谢

Answer 1

从来没听说过。

对于具有小整数的子集和，通常的伪多项式解的想法是，虽然存在非常多的组合，但是要考虑的总和相对较少。因此，我可以通过子集和存储我们到达该总和的最后一个索引和值的列表。然后，我可以找到我的目标答案，然后向后走数据结构，以创建中间子集总和和索引+值的列表，这些列表是在最终目标答案的路上。这为我们提供了一个数据结构，代表一个有限状态机来产生所有可能的答案。我们可以通过动态编程向前推进，以产生一个答案或一个答案计数，或者递归地枚举它以给出所有答案。 （知道所有答案通常都是很长的清单。）

浮点的问题是现在存在非常多的子集和非常大量的中间和。这个技巧不起作用。您可以将数字舍入到存储桶中，并生成接近目标的近似答案。但它们将是近似的，正确的答案仍然是大海捞针。

抱歉。