Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. I. ЗАДАЧИ ПАРТИИ В ОБЛАСТИ ЭКОНОМИЧЕСКОГО СТРОИТЕЛЬСТВА, СОЗДАНИЯ И РАЗВИТИЯ МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЙ БАЗЫ КОММУНИЗМА
  2. I. Составление математической модели задачи.
  3. I. Цели и задачи
  4. I. ЦЕЛИ И ЗАДАЧИ ОБУЧЕНИЯ ДИСЦИПЛИНЕ «НЕМЕЦКИЙ ЯЗЫК В СФЕРЕ ЮРИСПРУДЕНЦИИ» СТУДЕНТОВ-ЮРИСТОВ ЗАОЧНОЙ ФОРМЫ ОБУЧЕНИЯ
  5. II. ЗАДАЧИ ПАРТИИ В ОБЛАСТИ ПОДЪЕМА МАТЕРИАЛЬНОГО БЛАГОСОСТОЯНИЯ НАРОДА
  6. II. Основные задачи ФСБ России
  7. II. Основные цели и задачи Программы с указанием сроков и этапов ее реализации, а также целевые индикаторы и показатели, отражающие ход ее выполнения

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

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

;

§ иначе .

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

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

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

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

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

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

 


Дата добавления: 2015-08-20; просмотров: 172 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
РЕПЛИКИ!!!| поза для мужской фотосессии

mybiblioteka.su - 2015-2024 год. (0.006 сек.)