Бин-упаковка (или рюкзак?) Проблема

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) целевого интервала, то у исходной задачи есть где-то в этом интервале.

Answer 2

Вы не дали нам достаточно информации.Но, похоже, у вас неприятности, если вы действительно хотите ВЫХОДИТЬ каждую возможную комбинацию.Например, в соответствии с тем, что вы сказали нам, каждое число равно ~ 0,027.Если это так, то каждая коллекция из половины элементов удовлетворяет вашему критерию.Но есть 43 Выберите 21 таких наборов, что означает, что вы должны вывести как минимум 1052049481860 наборов.(слишком много, чтобы быть осуществимым)

Конечно, время работы будет не лучше, чем длина требуемого выхода.

Answer 3

На самом деле, есть более быстрый способ обойти это:

(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]

Кроме того, Аарон прав, так что это может быть или не быть возможным для вас