Условие задачи
Решить задачу о загрузке вручную методом динамического программирования
a) с помощью таблиц,
b) графически (на сети).
// грузоподъемность = 5
// доходы =
30 45 10 15
// вес предметов =
3 3 2 1
// подсказка:
f_opt = 75, решений: 2
Ответ
Метод обратной прогонки.
I этап. Условная оптимизация.
f4(L) = max(15x4); 0 x4 [5/1]; x4 = 0,1,2,3,4,5.
f4(0) = max[0*15] = 0
f4(1) = max[0*15, 1*15] = 15
f4(2) = max[0*15, 1*15, 2*15] = 30
f4(3) = max[0*15, 1*15, 2*15, 3*15] = 45
f4(4) = max[0*15, 1*15, 2*15, 3*15, 4*15] = 60
f4(5) = max[0*15, 1*15, 2*15, 3*15, 4*15, 5*15] = 75-означает из всех произведений макс найти число и это 75=5*15
Таблица 1 Расчет значения функции f1(L)