Bin-packing (or knapsack?) problem

Question

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.*

The brute-force method takes 2⁴³ to 2⁵⁰ steps, which isn't feasible. What's a good method to use here?

Edit: 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.

Answer 1

You haven't given us enough information. But it sounds like you are in trouble if you actually want to OUTPUT every possible combination. For example, consistent with what you told us are that every number is ~.027. If this is the case, then every collection of half of the elements with satisfy your criterion. But there are 43 Choose 21 such sets, which means you have to output at least 1052049481860 sets. (too many to be feasible)

Certainly the running time will be no better than the length of the required output.

Answer 2

Actually, there is a quicker way around this:

(python)

sums_possible = [(0, [])]
# sums_possible is an array of tuples like this: (number, numbers_that_yield_this_sum_array)
for number in numbers:
    sums_possible_for_this_number = []
    for sum in sums_possible:
        sums_possible_for_this_number.insert((number + sum[0], sum[1] + [number]))
    sums_possible = sums_possible + sums_possible_for_this_number

results = [sum[1] for sum in sums_possible if sum[0]>=L and sum[1]<=R]

Also, Aaron is right, so this may or may not be feasible for you

Answer 3

The basic idea is to convert it to an integer knapsack problem (which is easy).

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.