Несколько комбинаций, возвращаемых ограниченным алгоритмом Knapsack

Эта задача аналогична задаче об ограниченном рюкзаке (BKP). У нас около 300 различных блюд с такими параметрами как: ID, цена, важность/рейтинг, категория.

Например:

id  price  importance  type
-----------------------------
1   100     78         butter
2   50      89         milk
3   70      66         milk
4   66      50         butter

Мы хотим выбрать ТОП-10 лучших сочетаний продуктов, но при конкретной конфигурации хотим взять только 3 вида масла, 2 вида хлеба и 2 вида молока. Этот ТОП-10 комбинаций должен иметь наибольшую сумму важности. Также мы должны учитывать имеющийся бюджет.

Это немного отличается от задач с рюкзаком, потому что здесь нам нужны результаты ТОП-10, а не только лучшие. И каждый прием пищи/продукт одной и той же группы (например, сливочное масло) имеет разную цену и важность/рейтинг.


optimization algorithm knapsack-problem
person Vit D    schedule 20.08.2015    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Я полагаю, что цены целые и довольно небольшие, и вы думаете о каких-то школьных решениях DP.

ДП в целом

В алгоритмах динамического программирования для каждого состояния мы храним только одно лучшее частичное решение. Обычно мы не храним частичное решение физически: только его стоимость и некоторую простую информацию о возврате, чтобы восстановить ее позже. Мы не храним другие решения для состояния из-за свойства оптимальной подструктуры: любое частичное решение с худшей стоимостью имеет продолжения, которые хуже, чем такие же продолжения лучшего частичного решения.

Чтобы найти k лучших решений проблемы, вы можете просто сохранить k лучших частичных решений для каждого состояния DP. Если для какого-то состояния вообще меньше k решений, то сохраняем их все. Почему мы можем отбросить частичное решение, которое хуже, чем k других частичных решений? Потому что любое его продолжение будет хуже, чем такое же продолжение этих k лучших частичных решений.

Переходы в DP прямого стиля выполняются как обычно. Когда вы рассматриваете некоторое состояние, вы должны перебрать все его k лучших частичных решений и попытаться продолжить каждое из них всеми возможными способами (например, взять новый элемент или нет). Для каждого продолжения посмотрите на его состояние. Вставьте продолжение в отсортированный список лучших частичных решений. Если в результате получается k+1 частичных решений, худшее из них отбрасывается.

Наверняка вы не хотите хранить частичные решения в DP. Вместо этого сохраняйте только общую стоимость и информацию о возврате для каждого частичного решения. Информации о возврате должно быть достаточно, чтобы однозначно определить предыдущее частичное решение в DP. Таким образом, вы можете найти лучшие k решения. Кажется, что решение DP с k лучшими решениями требует в O(k) раз больше памяти и O(k^2) раз больше времени (или O(k log k)) для рюкзака по сравнению с поиском только одного лучшего решения.

Особая проблема

Мне кажется, что решать свою задачу следует двухуровневым алгоритмом:

  1. Запустите DP для задачи с ограниченным рюкзаком в каждой категории предметов. В результате вы получите k лучших комбинаций предметов категории с каждой общей стоимостью (и с ограниченным количеством предметов).
  2. Найдите оптимальную комбинацию решений, полученных на шаге 1. Необходимо взять по одному решению из каждой из рассматриваемых категорий.

Для одной категории решение DP для выбора s предметов из списка N предметов с размером рюкзака W, по-видимому, занимает O(s N W k^2) время. Объединение решений из категорий c на шаге 2 занимает O(c W^2 k^2), но его можно сократить до O(c W k log(W k)), если для слияния используется сбалансированное дерево.

person stgatilov    schedule 27.08.2015

arrow_upward
1
arrow_downward

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

Конечно, получить доказуемо лучшие 10 решений будет сложнее (буквально -- это явно NP-сложно). Один из подходов состоит в том, чтобы найти оптимальное решение, записать решение, добавить ограничение, чтобы исключить это решение, а затем решить. Повторяйте это несколько раз, пока не получите 10 лучших решений.

person John Coleman    schedule 20.08.2015