Уравнение Беллмана для задачи о рюкзаке

Пусть к началу -шага остаточная грузоподъемность равна s. Оптимальное управление определяется следующим образом:

если , то последний предмет можно положить в рюкзак, что соответствует оптимальному управлению

;

§ иначе .

Ясно, что оптимальный условный выигрыш на -ом шаге составит

Рассмотрим -й шаг. Предположим, что остаточная грузоподъемность равна . Если на этом шаге выбрать управление , то на начало последнего шага останется вес . Тогда выигрыш двух последних шагах будет равен

Нужно найти такое , при котором этот выигрыш максимален

где максимум берется по всем допустимым управлениям — управлениям, для которых верно ограничение. Напомним, что может принимать лишь два значения: 0 или 1.

Рассуждая далее аналогичным образом, приходим к рекуррентному уравнению

которое позволяет для любого -го шага вычислить условный оптимальный выигрыш и найти соответствующее ему условное оптимальное управление . Здесь — значение, при котором достигается максимум.

Дата добавления: 2015-08-20