algorithm - 具有 float 和目标总和或最接近目标总和的子集和问题的多项式\伪多项式算法

Question

我想知道是否存在一种算法来计算具有目标总和的排序列表(允许 float 和重复)的“所有可能组合”，如果没有任何组合等于目标总和，则该算法在多项式或伪多项式时间内将最近总和(下限)的“所有可能组合”返回到目标总和。我检查了 Balsub 算法“具有有限权重的背包问题的线性时间算法”以及具有多项式时间的“用于子集和的更快的伪多项式时间算法”，但我不确定这些问题在时间复杂度方面是否相同。

这是一个例子:

排序列表:{1.5, 2.25, 3.75, 3.81}
目标 = 3.79
结果:{1.5, 2.25}, {3.75} = 3.75

谢谢

Answer 1

据我所知不是。

小整数子集和的常用伪多项式解的想法是，虽然有非常多的组合，但要考虑的总和相对较少。因此，我可以按子集总和存储我们得出该总和的最后一个索引和值的列表。然后我可以找到我的目标答案，并向后遍历数据结构以创建中间子集总和和索引+值的列表，这些中间子集总和和索引+值正在通往最终目标答案的途中。这给了我们一个数据结构，代表一个有限状态机来产生所有可能的答案。我们可以通过动态规划向前推进，以生成一个答案或一系列答案，或者递归枚举它以给出所有答案。 (要知道所有答案通常都是一个很长的列表。)

float 的问题是现在有大量的子集和大量的中间和。那个把戏不管用。您可以将数字四舍五入到桶中，并生成接近目标的近似答案。但它们将是近似值，正确答案仍然是大海捞针。

对不起。