装箱（或背包？）的问题 [英] Bin-packing (or knapsack?) problem

问题描述

我有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 ⁴³ 2 ⁵⁰ 步骤，这是不可行的。什么是这里使用的好方法？

The brute-force method takes 2⁴³ to 2⁵⁰ 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.

这篇关于装箱（或背包？）的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！