Пусть имеются N видов грузов с номерами 
.
Единица груза j -го вида имеет все aj. Если груз j-го вида берется в количестве xj, то его ценность в общем случае составляет F (xj). Имеется «рюкзак», грузоподъемность которого равна B. Требуется загрузить рюкзак имеющимися грузами таким образом, чтобы вес его был не больше заданного B, а ценность «рюкзака» была максимальной.
Составим математическую модель задачи. Пусть xj – количество груза j -го вида, помещаемого в рюкзак. Тогда можно записать:
(3.15)
(3.16)
(3.17)
Здесь х j могут быть и целыми числами. В общем случае это задача нелинейного программирования с сепарабельной целевой функцией, следовательно, она может быть решена методом динамического программирования.
Для этого погрузку «рюкзака» можно интерпретировать как N -этапный процесс принятия решений: на 1-м этапе принимается решение о том, сколько нужно взять груза 1-го вида, на 2-ом этапе – сколько груза 2-го вида и т.д. Такая интерпретация наталкивает на возможность применения для решения задачи (3.15) – (3.17) метода динамического программирования. Для этого приведем задачу (3.15) – (3.17) к виду (3.4) – (3.7).
Для этого введем обозначения: 
– вес рюкзака перед погрузкой груза j -го вида груза или вес рюкзака после погрузки грузов видов 1, 2, …, j – 1.Очевидно, что
y 1 = 0. (3.18)
Текущий вес рюкзака определяется выражением
(3.19)
Текущий вес рюкзака 
в силу (3.16) удовлетворяет неравенству
£ B. (3.20)
Очевидно ограничения (3.18) – (3.20) эквивалентны ограничению (3.16), поэтому вместо модели (3.15) – (3.17) можно рассматривать модель (3.15), (3.17) – (3.20). Здесь ограничение (3.20) выводит эту модель за рамки модели (3.4) – (3.7). Для сведения задачи к общему виду задач динамического программирования, запишем (3.20) с учетом (3.19):
.
Отсюда следует: 
,
или окончательно с учетом (3.17):
(3.21)
В результате исходная модель (3.15) – (3.17) свелась к эквивалентной модели вида
(3.22)
(3.23)
(3.24)
(3.25)
Задача (3.22)-(3.25) является частным случаем общей задачи динамического программирования, в которой 
. Здесь ограничение (3.23) является рекуррентным и отражает процесс загрузки рюкзака, а неравенство (3.24) задает область возможных значений 
.
Рассмотрим решение задачи (3.22)-(3.25) методом динамического программирования:
1 шаг. Вычисляется величина
(3.26)
В результате решения серии задач максимизации получаем точки максимума 
и значения 
.
S -тый шаг (
). Вычисляются величины
(3.27)
В результате решения серии задач максимизации, получаем 
и 
. При s =1 решается только одна задача на максимум, т.к. значение - задано.
Для определения безусловных точек максимума, т.е. решения исходной задачи, проводим обратное движение алгоритма:
.
Отсюда:
.
Далее: 
. И так далее 
. Причем 
есть максимальное значение целевой функции.
Наличие условия целочисленности переменных xj и 
упрощает решение задачи. В этом случае 
. Здесь [ В ] указывает на то, что берется целая часть числа. Если не целые, то 
.
Пример:
Имеется свободный капитал в размере 4 млн. у.е. Этот капитал может быть распределен между 4-мя предприятиями, причем распределение осуществляется только целыми частями (0, 1, 2, 3 или 4 млн. у.е.). Прибыль, получаемая каждым предприятием при инвестировании в него определенной суммы, указана в таблице.
| Предпр. Капитал | 0 млн. у.е. | 1 млн. у.е. | 2 млн. у.е. | 3 млн. у.е. | 4 млн. у.е. |
| 1-е предпр. | 0 | 10 | 17 | 25 | 36 |
| 2-е предпр. | 0 | 11 | 16 | 25 | 35 |
| 3-е предпр. | 0 | 10 | 18 | 24 | 34 |
| 4-е предпр. | 0 | 9 | 19 | 26 | 35 |
Требуется распределить инвестиции между предприятиями из условия максимальной общей прибыли.
Обозначим: х j - количество капиталовложений, выделенных j -тому предприятию (
). Тогда прибыль, записанная в таблице, можно обозначить как Fj (xj) (). Например, F1(0)=0; F1(1)=10; F1(2)=17 и т.д..... F2(0)=0; F2(1)=11; F4(4)=35.
Тогда математическая модель примет вид:
х j ≥ 0 – целые, ()
Данная модель является частным случаем задачи о загрузке рюкзака, где N =4, В=4, а j =1 (). Введя новую переменную yj - израсходованные средства до выделения капиталовложений j -тому предприятию, приведем исходную модель к виду задачи динамического программирования:
; ()
y 1 = 0;
; ()
Решение задачи проведем в соответствии с алгоритмом динамического программирования:
Шаг.
1) Зафиксируем y 4 =0. Тогда допустимые значения x 4 Î [0, 4-0] =[0,1,2,3,4].
1.1) x 4 =0. Тогда F 4 (0)=0.
1.2) x 4 =1. F 4 (1)=9.
1.3) x 4 =2. F 4 (2)=19.
1.4) x 4 =3. F 4 (3)=26
1.5) x 4 =4. F 4 (4)=35.
Максимальное значение 
, и достигается оно при x 4 =4. Таким образом, заполняется первая строчка таблицы.
2) Зафиксируем y4=1. Тогда допустимые значения x 4 Î [0, 4-1]= [0,1,2,3].
2.1) x 4 =0. Тогда F 4 (0)=0.
2.2) x 4 =1. F 4 (1)=9.
2.3) x 4 =2. F 4 (2)=19.
2.4) x 4 =3. F 4 (3)=26.
Максимальное значение 
, и достигается оно при x 4 =3. Таким образом, заполняется вторая строка таблицы.
Далее аналогично фиксируем y 4 =2, y 4 =3, y 4 =4. Заполняем оставшиеся строки таблицы.
Таблица шага №1.
| y4 x4 | 0 | 1 | 2 | 3 | 4 | 
| 
|
| 0 | 0 | 9 | 19 | 26 | 35 | 35 | 4 |
| 1 | 0 | 9 | 19 | 26 | - | 26 | 3 |
| 2 | 0 | 9 | 19 | - | - | 19 | 2 |
| 3 | 0 | 9 | - | - | - | 9 | 1 |
| 4 | 0 | - | - | - | - | 0 | 0 |
Шаг.
1) Зафиксируем y 3 =0. Тогда допустимые значения x 3 Î [0, 4-0] =[0,1,2,3,4].
1.1) x 3 =0. Тогда F 3 (0)=0. Определим значение второго слагаемого: 
при y 3 =0 и x 3 =0. Найдем y 4 =0+0=0. Тогда, обратившись к таблице шага 1, увидим, что . Следовательно, F 3 (0)+ 
=0+35=35. Этот результат заносим в таблицу шага 2 в ячейку, соответствующую y 3 =0 и x 3 =0.
1.2) x 3 =1. Аналогично: F 3 (1)=10. Найдем y 4 = y 3 + x 3 =0+1=1. Из таблицы шага 1 определим: = 
. Сумма F 3 (1)+ 
=10+26=36.
1.3) x 3 =2. F 3 (2)=18. y 4 =0+2=2. Þ = 
= 19. Тогда F 3 (2)+ =18+19=37.
1.4) x 3 =3. F 3 (3)=24, y 4 =0+3=3. Þ = 
= 9. Тогда F 3 (3)+ =24+9=33.
1.5) x 3 =4. F 3 (4)=34. y 4 =0+4=4. Þ = 
=0. Тогда F 3 (4)+ =34+0=34.
Максимальное значение 
=37, и достигается оно при x 3 =2. Первая строчка таблицы заполнена.
2) Зафиксируем y 3 =1. Тогда допустимые значения x 3 Î [0, 4-1]= [0,1,2,3].
2.1) x 3 =0. F 3 (0)=0. y 4 =1+0=1. Þ = =26. Тогда F 3 (0)+ =0+26=26.
2.2) x 3 =1. F 3 (1)=10. y 4 =1+1=2. Þ = = =19. Тогда F 3 (1)+ =10+19=29.
2.3) x 3 =2. F 3 (2)=18. y 4 =1+2=3. Þ = =9. Тогда F3(2)+ =18+9=27.
2.4) x 3 =3. F 3 (3)=24 y 4 =1+3=4. Þ = =0. Тогда F 3 (3)+ =24+0=24.
Максимальное значение 
, и достигается оно при x 3 =1. Таким образом, заполняется вторая строка таблицы.
3) Зафиксируем y 3 =2. Тогда допустимые значения x 3 Î [0, 4-2]= [0,1,2].
3.1) x 3 =0. F 3 (0)=0. y 4 =2+0=2. Þ f4(2) = 19. F 3 (0)+ f4(2) =0+ 19 = 19.
3.2) x 3 =1. F 3 (1)=10. y 4 =2+1=3. Þ =9. F 3 (1)+ =10+9= 1 9.
3.3) x 3 =2. F 3 (2)=18. y 4 = 2 +2=3. Þ = 0. F 3 (2)+ =18+ 0 = 18.
Максимальное значение 
достигается при двух возможных значениях x 3: x 3 =1 и x 3 =0. В таблицу можно занести любое из них. Таким образом, заполняется третья строка таблицы.
Далее аналогично фиксируем y 3 =3, y 3 =4. Заполняем оставшиеся строки таблицы.
Таблица шага №2.
| y3 x3 | 0 | 1 | 2 | 3 | 4 | 
| 
|
| 0 | 35 | 36 | 37 | 33 | 34 | 37 | 2 |
| 1 | 26 | 29 | 27 | 24 | - | 29 | 1 |
| 2 | 19 | 19 | 18 | - | - | 19 | 0 (или 1) |
| 3 | 9 | 10 | - | - | - | 10 | 1 |
| 4 | 0 | - | - | - | - | 0 | 0 |
Шаг.
Все вычисления производятся аналогично шагу 2. Не останавливаясь более подробно на этапах решения подзадачи данного шага, приведем получившуюся в результате таблицу.
Таблица шага №3.
| y2 x2 | 0 | 1 | 2 | 3 | 4 | 
| 
|
| 0 | 37 | 40 | 35 | 35 | 35 | 40 | 1 |
| 1 | 29 | 30 | 26 | 25 | - | 30 | 1 |
| 2 | 19 | 21 | 16 | - | - | 21 | 1 |
| 3 | 10 | 11 | - | - | - | 11 | 1 |
| 4 | 0 | - | - | - | - | 0 | 0 |
Шаг.
Последний шаг интересен тем, что здесь решается единственная задача максимизации при заданном y 1 =0.
y 1 =0. Следовательно x 1 Î [0, 4-0]= [0,1,2,3,4]. Выполняя все действия, аналогично предыдущим шагам, получим таблицу последнего шага, состоящую из единственной строки, соответствующей y 1 =0.
Таблица шага №4.
| y1 x1 | 0 | 1 | 2 | 3 | 4 | 
| 
|
| 0 | 40 | 40 | 38 | 36 | 36 | 40 | 0 (или 1) |
Далее проводим обратное движение алгоритма:
1) y1=0, x1*=0, Þ y2*= y1+ x1*=0+0=0.
2) Определяем значение x2* из таблицы шага № 3 по найденному y 2 *=0. Значению y 2 = y 2 *=0 соответствует значение x 2 (y 2)=1. Следовательно, x 2 *=1. Далее можно определить y 3 *= y 2 *+ x 2 *=0+1=1.
3) Аналогично, обращаясь к таблице шага №2, найдем: x 3 *= x 3 (1)=1, Þ y 4 *= y 3 *+ x 3 *=1+1=2.
4) Из таблицы шага №1: x 4 *= x 4 (2)=2.
Окончательно имеем: первому предприятию средства не выделяются (x 1 *=0), второму выделяется 1 млн. у.е. (x 2 *=1), третьему предприятию – 1 млн. у.е. (x 3 *=1), и четвертому – 2 млн. у.е. (x 4 *=2). При этом значение целевой функции (общая прибыль по всем 4-м предприятиям) составит:
= =40.
