Cha*_*les 5 algorithm optimization computer-science
我有一个43到50个数字的集合,范围从0.133到0.005(但主要是在小方面).如果可能的话,我想找到L和R之间总和的所有组合,它们非常接近.*
蛮力方法需要2 43至2 50步,这是不可行的.在这里使用什么好方法？
编辑:组合将用于计算并丢弃.(如果你正在编写代码,你可以假设它们只是输出;我会根据需要进行修改.)组合的数量可能太大而无法保存在内存中.
* L = 0.5877866649021190081897311406,R = 0.5918521703507438353981412820.
基本思想是将其转换为整数背包问题（这很容易）。
选择一个小的实数e，并将原始问题中的数字舍入为可用k*e整数表示的数字k。越小e，整数就越大（效率权衡），但修改后的问题的解决方案将更接近原始问题的解决方案。其中e=d/(4*43)d 是目标间隔的宽度，应该足够小。
如果修改后的问题有一个精确解，其总和等于e目标区间的中间（四舍五入为 ），则原始问题在该区间内的某个位置有一个解。