Условие
Самолёт вмещает не более 14 тонн. Можно взять любое неотрицательное целое число контейнеров типов A,B,C,D. Их веса: 2, 3, 5, 6 тонн, прибыли: 5, 6, 13, 16 тысяч рублей. Найдите оптимальную загрузку, запишите модель и объясните динамическое программирование.
Решение источника
Источник указывает загрузку A+D+D и прибыль 37, но приведённая рекурсия не содержит перехода, сохраняющего решение без очередного типа контейнера.
Редакционное объяснение
Модель: max(5xA + 6xB + 13xC + 16xD) при 2xA + 3xB + 5xC + 6xD≤14, все 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 | 6 |
| 4 | 10 |
| 5 | 13 |
| 6 | 16 |
| 7 | 18 |
| 8 | 21 |
| 9 | 23 |
| 10 | 26 |
| 11 | 29 |
| 12 | 32 |
| 13 | 34 |
| 14 | 37 |
D(14)=37. Восстановление решения даёт A+D+D: масса 2+6+6=14, прибыль 5+16+16=37. Вектор количества контейнеров равен (1,0,0,2).
При таблице по типам нужна рекурсия Fᵢ(w)=max(Fᵢ₋₁(w), Fᵢ(w−wᵢ)+pᵢ) для w≥wᵢ; если w<wᵢ, остаётся Fᵢ₋₁(w). Первый член сохраняет возможность не использовать тип i. Его отсутствие в записи источника делает рекурсию неполной.
Проверка
Независимый полный перебор 55 допустимых комбинаций количеств совпал с динамической таблицей: максимум 37, оптимальный вектор единственный. Для него масса не превышает 14; прибыль вычисляется прямой подстановкой.
Что не следует из ответа
Выбор типа с наибольшей прибылью на тонну не является общим доказательством: целые контейнеры оставляют остатки вместимости. В этой модели каждый тип можно брать многократно. Для задачи «каждый предмет не более одного раза» переход с добавлением предмета использует предыдущий набор предметов.
Борис Демешев и участники · «Задачки по методам оптимальных решений», задание и исходное решение, строка 3003 · CC0 1.0. Адаптация damirock.com: написана полная динамическая рекурсия с доказательством, рассчитаны все вместимости и исправлен пропущенный переход.