0/1 Рюкзак с несколькими переменными: какой алгоритм?

Question

Я должен реализовать решение задачи 0/1 Knapsack с ограничениями. Моя проблема будет иметь в большинстве случаев несколько переменных (~ 10-20, самое большее 50).

Я помню из университета, что существует ряд алгоритмов, которые во многих случаях работают лучше, чем грубая сила (я имею в виду, например, алгоритм ветвления и привязки).

Поскольку моя проблема относительно небольшая, мне интересно, есть ли значительное преимущество с точки зрения эффективности при использовании сложного решения, а не грубой силы.

Если это помогает, я программирую на Python.

Answer 1

Грубые силы будут работать отлично для 10 переменных, но, скажем, 40, вы получите около 1000 000 000 000 возможных решений, которые, вероятно, слишком долго будут перечисляться. Я бы рассмотрел приближенные алгоритмы, например. алгоритм полиномиального времени (см., например, http://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf) или использовать алгоритм поиска, такой как ветка и связанный, возможно, с дополнительной эвристикой.

Answer 2

Вы можете использовать псевдополиномиальный алгоритм, который использует динамическое программирование, если сумма весов достаточно мала. Вы просто вычислите, можете ли вы получить вес X с первыми Y элементами для каждого X и Y. Это выполняется во времени O (NS), где N - количество элементов, а S - сумма весов.

Другая возможность - использовать средний подход. Элементы разделов на две половины и: Для первого тайма возьмите все возможные комбинации предметов (в каждой половине есть две возможные комбинации (N/2)) и сохраните свой вес в некотором наборе. Для второй половины используйте все возможные комбинации предметов и проверьте, есть ли комбинация в первой половине с подходящим весом. Это должно работать в O (2^(N/2)) времени.

Answer 3

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

Если у вас гарантировано до 20 переменных, вы проверите не более 1 миллиона решений (2^20 = 1M). Следовательно, грубая сила возможна, и ни один другой алгоритм не вернет лучшее решение.

Эвристика велика, но их следует использовать, только если у нас нет точного решения проблемы. Существует отличная книга, которая может вам помочь: How to Solve it, by Michalewicz.