我有43至50个号码,从0.133到0.005(但大多是小方)的集合。我想了解,如果可能的话,有L和R之间的总和所有组合,这是非常接近的。*
I have a collection of 43 to 50 numbers ranging from 0.133 to 0.005 (but mostly on the small side). I would like to find, if possible, all combinations that have a sum between L and R, which are very close together.*
蛮力方法需要2 43 2 50 步骤,这是不可行的。什么是这里使用的好方法?
The brute-force method takes 243 to 250 steps, which isn't feasible. What's a good method to use here?
编辑:组合将在计算中被使用和丢弃。 (如果你正在写code,你可以假设他们只是输出;根据需要,我会修改)的组合数将presumably远远太大,保留在内存中
The combinations will be used in a calculation and discarded. (If you're writing code, you can assume they're simply output; I'll modify as needed.) The number of combinations will presumably be far too large to hold in memory.
* 的L = 0.5877866649021190081897311406,R = 0.5918521703507438353981412820。
* L = 0.5877866649021190081897311406, R = 0.5918521703507438353981412820.
其基本思想是将其转换为整数背包问题(很简单)。
The basic idea is to convert it to an integer knapsack problem (which is easy).
选择一个小的实数电子
和整数点位在原始问题的人重新presentable为 K * E
整数 K
。较小的电子
,较大的整数会(效率的权衡),但修改后的问题的解决将是更接近你原来的。一个 E = D /(4 * 43)
其中d是你的目标区间的宽度应足够小。
Choose a small real number e
and round numbers in your original problem to ones representable as k*e
with integer k
. The smaller e
, the larger the integers will be (efficiency tradeoff) but the solution of the modified problem will be closer to your original one. An e=d/(4*43)
where d is the width of your target interval should be small enough.
如果修改后的问题具有求和中间一个确切的解决方案(四舍五入至电子
)的目标区间,那么原来的问题,有一个地方的区间内。
If the modified problem has an exact solution summing to the middle (rounded to e
) of your target interval, then the original problem has one somewhere within the interval.
上一篇:聚类问题问题