Построение математической модели решения задач

Имеется набор из N предметов. Пусть MaxW — объем рюкзака, Pi — стоимость i-го предмета, Wi — вес i-го предмета. Value [W, i] - максимальная сумма, которую надо найти. Суть метода динамического программирования на каждом шаге по весу 1.

Если его взять то вес станет W-Wi, тогда Value[W, i] = Value[W — Wi, i-1] + Pi (для Value[W — Wi, i-1]) решение уже найдено остается только прибавить Pi.

Если его не брать то вес останется тем же и Value[W, i] = Value [W — Wi, i-1]. =Из двух вариантов выбирается тот, который дает наибольший результат. Рассмотрим алгоритм подробнее.

Рис 1.1 Решение примера

Рис 1.2 Решение примера

Рис 1.3 Решение примера

Динамическое программирование для задачи о рюкзаке дает точное решение, причем одновременно вычисляются решения для всех размеров рюкзака от 1 до MaxW, но какой ценой? Для хранения таблицы стоимости и запоминания того, брался каждый предмет или нет, требуется порядка O (N*MaxW) памяти, временная сложность равна O (N*MaxW);

Опишем основную логику решения:

{Загружаем рюкзак если его вместимость = Weight} for Weight:=1 to MaxW do begin.

for i:=1 to N do {берем предметы с 1 по N}.

{если вес предмета больше Weight}.

{или предыдущий набор лучше выбираемого}.

if (W[i]>Weight) or (Value[Weight, i-1] >=.

Value[Weight-W[i], i-1]+P[i]) then begin.

{Тогда берем предыдущий набор}.

Value[Weight, i]: =Value[Weight, i-1];

{говорим что вещь i не взята}.

Take [Weight, i]: = false;

End.

{иначе добавляем к предыдущему набору текущий предмет}.

Else begin.

Value [Weight, i]: =Value [Weight — W[i], i-1].

+P[i];

{говорим что вещь i взята}.

Take [Weight, i]: = true;

End; End;

Блок схема основного алгоритма Как было сказано ранее, алгоритм динамического программирования для `рюкзака' дает точное решение путем использования дополнительной памяти O (N*MaxW), временная сложность алгоритма так же будет порядка O (N*MaxW).