Условие
Самолёт вмещает не более 15 тонн. Можно взять любое неотрицательное целое число контейнеров типов A,B,C,D. Их веса: 2, 3, 4, 6 тонн, прибыли: 5, 7, 11, 17 тысяч рублей. Найдите оптимальную загрузку, запишите модель и объясните динамическое программирование.
Решение источника
Источник задаёт целочисленную модель, но не выписывает оптимальную загрузку. В рекурсии отсутствует сравнение с решением, в котором очередной тип не используется.
Редакционное объяснение
Модель: max(5xA + 7xB + 11xC + 17xD) при 2xA + 3xB + 4xC + 6xD≤15, все x — неотрицательные целые числа. Это целочисленная задача; снятие требования целочисленности меняет множество допустимых загрузок.
Пусть D(w) — максимальная прибыль при вместимости не более w со всеми четырьмя типами. Положим D(0)=0. Для w≥1 используем D(w)=max(0, maxᵢ:wᵢ≤w {D(w−wᵢ)+pᵢ}). Любая непустая загрузка содержит какой-то последний контейнер; его удаление оставляет допустимую загрузку на w−wᵢ. Обратно, добавление контейнера к оптимальному остатку даёт допустимую кандидатуру. Это доказывает рекурсию.
| Вместимость w, т | D(w), тыс. руб. |
|---|---|
| 0 | 0 |
| 1 | 0 |
| 2 | 5 |
| 3 | 7 |
| 4 | 11 |
| 5 | 12 |
| 6 | 17 |
| 7 | 18 |
| 8 | 22 |
| 9 | 24 |
| 10 | 28 |
| 11 | 29 |
| 12 | 34 |
| 13 | 35 |
| 14 | 39 |
| 15 | 41 |
D(15)=41. Восстановление решения даёт B+D+D: масса 3+6+6=15, прибыль 7+17+17=41. Вектор количества контейнеров равен (0,1,0,2).
При таблице по типам нужна рекурсия Fᵢ(w)=max(Fᵢ₋₁(w), Fᵢ(w−wᵢ)+pᵢ) для w≥wᵢ; если w<wᵢ, остаётся Fᵢ₋₁(w). Первый член сохраняет возможность не использовать тип i. Его отсутствие в записи источника делает рекурсию неполной.
Проверка
Независимый полный перебор 75 допустимых комбинаций количеств совпал с динамической таблицей: максимум 41, оптимальный вектор единственный. Для него масса не превышает 15; прибыль вычисляется прямой подстановкой.
Что не следует из ответа
Выбор типа с наибольшей прибылью на тонну не является общим доказательством: целые контейнеры оставляют остатки вместимости. В этой модели каждый тип можно брать многократно. Для задачи «каждый предмет не более одного раза» переход с добавлением предмета использует предыдущий набор предметов.
Борис Демешев и участники · «Задачки по методам оптимальных решений», задание и исходное решение, строка 3055 · CC0 1.0. Адаптация damirock.com: написана полная динамическая рекурсия с доказательством, рассчитаны все вместимости и исправлен пропущенный переход.