Алгоритм определения лучших комбинаций - Bin Packing - PullRequest
2 голосов
/ 11 сентября 2010

Учитывая набор элементов, каждый из которых имеет значение, определите номер каждого элемента, включаемого в коллекцию, чтобы общее значение было меньше или равно заданному пределу, а общее значение было как можно большим.

Пример:

Product A = 4
Product B = 3
Product C = 2
Product D = 5

If Total Capacity = 10.5 , then the combination of B,C,D will be selected.
If Total Capacity = 12.5 , then the combination of A,B,D will be selected.
If Total Capacity = 17 , then the combination of A,B,C,D will be selected.

Я ищу алгоритм (например, упаковку в рюкзак или в корзину) для определения комбинации. Любая помощь приветствуется.

1 Ответ

5 голосов
/ 11 сентября 2010

Вы говорите, что это "как рюкзак".Насколько я понимаю, это особый случай ограниченной задачи о ранце , называемый проблемой ранца 0-1.

Это NP-полная.

Есть многоспособов вы могли бы попытаться решить это.См. Этот связанный вопрос для одного подхода:

Если у вас есть только четыре элемента, топросто тестирование всех возможностей должно быть достаточно быстрым для большинства целей.

...