значения j. Для
значения j.
Для получения наилучшего решения необходимо выбрать лучшую из этих двух возможностей. Поэтому рекуррентное соотношение при i?1 и j?1 имеет вид
T(i,j)=T(i-1,j) при j<M[i] и
T(i,j)=max(T(i-1,j),T(i-1,j-M[i]) + C[i]) при j?M[i].
Пусть заданы следующие значения стоимости и массы для 5 предметов:
C[1] = 5, M[1] = 4;
C[2] = 7, M[2] = 5;
C[3] = 4, M[3] = 3;
C[4] = 9, M[4] = 7;
C[5] = 8, M[5] = 6.
Таблица значений функции T, которую мы также назовем T, выглядит следующим образом:
i\j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 5 5 5 5 5 5 5 5 5 5 5 5 5
2 0 0 0 0 5 7 7 7 7 12 12 12 12 12 12 12 12
3 0 0 0 4 5 7 7 9 11 12 12 12 16 16 16 16 16
4 0 0 0 4 5 7 7 9 11 12 13 14 16 16 18 20 21
5 0 0 0 4 5 7 8 9 11 12 13 15 16 17 19 20 21
Следовательно, решение задачи T(5,16)=21. Однако
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
