Polynomial\Pseudo-Polynomial 具有浮点数和目标总和或最接近目标总和的子集和问题的算法
Polynomial\Pseudo-Polynomial Algorithm for Subset-Sum Problem with float and target sum or nearest sum to the target sum
我想知道是否存在一种算法来计算 "all possible combinations" 具有目标总和的排序列表（允许浮动和重复），如果没有任何组合等于目标总和，算法 return "all possible combinations" 在多项式或伪多项式时间内最接近目标和的和（下限）。
我用多项式时间检查了 Balsub 算法 "Linear Time Algorithms for Knapsack Problems with Bounded Weights" 和 "A Faster Pseudopolynomial Time Algorithm for Subset Sum"，但我不确定这些问题在时间复杂度方面是否相同。
这是一个例子：
Sorted List: {1.5, 2.25, 3.75, 3.81}
Target = 3.79
Results: {1.5, 2.25}, {3.75} = 3.75
谢谢
据我所知没有。
小整数子集和的常用伪多项式解的想法是，虽然有非常多的组合，但要考虑的总和相对较少。因此，我可以按子集总和存储我们得出该总和的最后一个索引和值的列表。然后我可以找到我的目标答案，并向后遍历数据结构以创建中间子集总和和索引+值的列表，这些中间子集总和和索引+值正在通往最终目标答案的途中。这给了我们一个数据结构，代表一个有限状态机来产生所有可能的答案。我们可以通过动态规划向前推进，以生成一个答案或一系列答案，或者递归枚举它以给出所有答案。 （要知道所有的答案通常都是一个很长的列表。）
浮点数的问题是现在有大量的子集和大量的中间和。那个把戏不管用。您可以将数字四舍五入到桶中，并生成接近目标的近似答案。但它们将是近似值，正确答案仍然是大海捞针。
对不起。
我想知道是否存在一种算法来计算 "all possible combinations" 具有目标总和的排序列表（允许浮动和重复），如果没有任何组合等于目标总和，算法 return "all possible combinations" 在多项式或伪多项式时间内最接近目标和的和（下限）。 我用多项式时间检查了 Balsub 算法 "Linear Time Algorithms for Knapsack Problems with Bounded Weights" 和 "A Faster Pseudopolynomial Time Algorithm for Subset Sum"，但我不确定这些问题在时间复杂度方面是否相同。
这是一个例子：
Sorted List: {1.5, 2.25, 3.75, 3.81}
Target = 3.79
Results: {1.5, 2.25}, {3.75} = 3.75
谢谢
据我所知没有。
小整数子集和的常用伪多项式解的想法是，虽然有非常多的组合，但要考虑的总和相对较少。因此，我可以按子集总和存储我们得出该总和的最后一个索引和值的列表。然后我可以找到我的目标答案，并向后遍历数据结构以创建中间子集总和和索引+值的列表，这些中间子集总和和索引+值正在通往最终目标答案的途中。这给了我们一个数据结构，代表一个有限状态机来产生所有可能的答案。我们可以通过动态规划向前推进，以生成一个答案或一系列答案，或者递归枚举它以给出所有答案。 （要知道所有的答案通常都是一个很长的列表。）
浮点数的问题是现在有大量的子集和大量的中间和。那个把戏不管用。您可以将数字四舍五入到桶中，并生成接近目标的近似答案。但它们将是近似值，正确答案仍然是大海捞针。
对不起。