带浮点数的子集和
Subset Sum with Floats
假设您有一组浮点数，例如
4.2 ; 2.6 ; 6.9 ; 1.1
然后判断是否存在和等于5.3的Subset，如果存在，return这个集合。
所有给定的数字始终保留一位小数。
一种方法是通过蛮力：生成原始集合的所有组合，并分别检查每个组合的总和。然而，这是相当糟糕的，通常这种问题是使用动态规划来解决的——实际上，这是 knapsack problem.
的一个特殊问题。
我的问题是，由于我们正在考虑浮动，您将如何有效地解决这个问题？
标准的动态规划方法似乎不是一个好的选择，因为它需要我构建一个 table 来计算从 0 到 0 的所有可能的 float 值目标数字（本例中为 5.3）。因为我们知道我们总是有一个小数点，所以我想可以想象这样 table:
0 | 0.1 | 0.2 | ... | 5.3
4.2
2.6
6.9
1.1
但我认为这不会很好地扩展...（这里，5.3 只是为了简单起见的一个值，我没有任何关于实践中目标值约束的信息。）
关于如何解决这个问题有什么想法吗？
您确实需要将其简化为整数情况才能获得您可能想要的结果。
对于最常见的浮点格式，即基于 IEEE 754 标准二进制浮点的格式，答案很简单。没有一组总和为 5.3 的浮点数。唯一可精确表示的具有一位小数的值是小数点后的数字为 0 或 5 的值。
另一方面，如果您要将每个输入乘以 10 并四舍五入到最接近的整数，您可以像求解整数一样求解它。
假设您有一组浮点数，例如
4.2 ; 2.6 ; 6.9 ; 1.1
然后判断是否存在和等于5.3的Subset，如果存在，return这个集合。
所有给定的数字始终保留一位小数。
一种方法是通过蛮力：生成原始集合的所有组合，并分别检查每个组合的总和。然而，这是相当糟糕的，通常这种问题是使用动态规划来解决的——实际上，这是 knapsack problem.
的一个特殊问题。我的问题是，由于我们正在考虑浮动，您将如何有效地解决这个问题？
标准的动态规划方法似乎不是一个好的选择，因为它需要我构建一个 table 来计算从 0 到 0 的所有可能的 float 值目标数字（本例中为 5.3）。因为我们知道我们总是有一个小数点，所以我想可以想象这样 table:
0 | 0.1 | 0.2 | ... | 5.3
4.2
2.6
6.9
1.1
但我认为这不会很好地扩展...（这里，5.3 只是为了简单起见的一个值，我没有任何关于实践中目标值约束的信息。）
关于如何解决这个问题有什么想法吗？
您确实需要将其简化为整数情况才能获得您可能想要的结果。
对于最常见的浮点格式，即基于 IEEE 754 标准二进制浮点的格式，答案很简单。没有一组总和为 5.3 的浮点数。唯一可精确表示的具有一位小数的值是小数点后的数字为 0 或 5 的值。
另一方面，如果您要将每个输入乘以 10 并四舍五入到最接近的整数，您可以像求解整数一样求解它。