algorithm - 装箱(或背包？)问题

Question

我收集了 43 到 50 个数字，范围从 0.133 到 0.005(但大部分偏小)。如果可能的话，我想找到 L 和 R 之间总和非常接近的所有组合。*

蛮力法需要 2⁴³ 到 2⁵⁰ 步，这是不可行的。这里使用什么方法比较好？

编辑:组合将用于计算并被丢弃。 (如果您正在编写代码，您可以假设它们只是输出；我会根据需要进行修改。)组合的数量可能太大而无法保存在内存中。

* L = 0.5877866649021190081897311406，R = 0.5918521703507438353981412820。

Answer 1

基本思想是将其转换为整数背包问题(这很容易)。

选择一个小实数 e 并将原始问题中的数字四舍五入为可表示为 k*e 和整数 k 的数字。 e 越小，整数就越大(效率权衡)，但修改后的问题的解决方案将更接近您的原始问题。 e=d/(4*43) 其中 d 是目标间隔的宽度应该足够小。

如果修改后的问题有一个精确解求和到目标区间的中间(四舍五入为 e)，那么原始问题在区间内某处有一个。