Knapsack_PLN_DP1. Упаковка вещей в ранец / рюкзак, Данциг. Максимум ценных вещей в рюкзаке при ограниченной вместимости. Объемное агрегированное планирование. 1 интервал.

Постановка задачи

Задача о ранце (или задача о рюкзаке) – одна из NP-полных задач комбинаторной оптимизации. Своё название получила от конечной цели: уложить как можно большее число ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена. С различными вариациями задачи о ранце можно столкнуться в экономике, прикладной математике, криптографии и логистике.

В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес» требуется отобрать подмножество с максимальной полной стоимостью, соблюдая при этом ограничение на суммарный вес.

Дано:

•  Ранец заданной вместимости.

•  Набор вещей, которые можно положить в ранец. Каждая вещь имеет две характеристики: масса (объем) и стоимость (ценность).

Требуется:

Выбрать из этих вещей такой набор, чтобы суммарный вес не превосходил заданной вместимости ранца, а суммарная ценность (стоимость) была максимальна.

кратко

Число установок соответствует числу вещей, которые можно положить в ранец.

Установка отражает отдельную вещь, которую можно положить в ранец. Операциями установки является выбор предмета или не выбор – положить вещь в ранец или нет. Потоками операции являются характеристики вещи, которые влияют на выбор вещи – вес.

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

кратко

Рисунок. Общий вид потоковой схемы объекта «с именами»

кратко

Параметры вещей, выбираемых для сборки ранца: Вещь1 – вес 3, ценность 1; Вещь2 – вес 4, ценность 6; Вещь3 – вес 5, ценность 4; Вещь4 – вес 8, ценность 7; Вещь5 – вес 9, ценность 6;

Объем ранца – 13.

Критерий «Выполнение» – максимум стоимости вещей положенных в ранец вещей. Для этого стоимости операций приводятся к виду, пригодному для этого критерия. Из-за условий критерия «Выполнения» – неотрицательности и оптимизации к минимуму, стоимость модифицируется соответствующим образом.

кратко

Вещи для ранца

Рисунок. Фрагмент формы – стадия, установка, операция, поток

Примечание. Видны цены операций, и место, которое занимает вещь в ранце.

Ранец, его вместимость:

Рисунок. Фрагменты формы – стадия, емкость

кратко

Фрагменты расписания

Рисунок. Фрагмент расписания выполнения операций

Примечание. Для сборки ранца лучше всего выбрать вещи 2 и 4.

Пользовательские отчеты по работе установок и состоянию емкостей

Отчет «время вниз» от установок:

Рисунок. Фрагмент отчета «время вниз» от установок

Отчет «время вниз» от емкостей:

Рисунок. Фрагмент отчета «время вниз» от емкостей

Объяснения решения

Рисунок. Фрагмент трассы объяснений хода рассуждений Решателя DP

кратко