На складе имеется 5 неделимых предметов. Для каждого предмета известна его стоимость (в рублях) и масса (в кг). Величины стоимости и массы являются натуральными числами. Ваша цель состоит в том, чтобы определить максимальную суммарную стоимость предметов, которые можно унести со склада при условии, что суммарная масса предметов не должна превышать 16 кг.

Пусть элемент C_i таблицы C соответствует стоимости i-го предмета, а элемент M_i таблицы M - массе i-го предмета. Будем считать, что предметы пронумерованы в порядке их следования в таблицах.

Пусть T обозначает функцию, значение которой соответствует решению нашей задачи. Аргументами функции является количество предметов (по этому аргументу можно определить их стоимости и массы соответствующих предметов), а также максимальная суммарная масса, которую можно унести.

Определим подзадачи T(i, j), где i обозначает количество начальных предметов, из которых можно осуществлять выбор, а j определяет максимально возможную суммарную массу уносимых предметов. Отметим, что определенный таким образом первый параметр i определяет как количество предметов для подзадачи, так и значения их стоимостей и масс, определяемых из таблиц C и M.

Определим сначала начальные значения функции T. При нулевых значениях одного из аргументов значение функции равно нулю:

T(0,0)=0

T(0,j)=0 при j³1,

T(i,0)=0 при i³1.

Определим возможные значения функции T(i, j) при ненулевых значениях аргументов.

Решение подзадачи, соответствующей функции T(i, j) может быть сведено к двум возможностям: уносится ли при наилучшем решении предмет с номером i или нет.

Если предмет не уносится, то решение задачи с i предметами сводится к решению подзадачи с i-1 предметами, т. е.

T(i,j)=T(i-1,j).

Если предмет c номером i уносится, то это уменьшает максимально возможную суммарную массу для i-1 первых предметов на величину M[i], одновременно при этом увеличивая значение решения для оставшихся предметов T(i-1,j-M[i]) на величину C[i], т. е.

T(i,j)=T(i-1,j-M[i])+C[i].

При этом необходимо учитывать, что вторая ситуация возможна только тогда, когда масса i-го предмета не больше значения 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, выглядит следующим образом:

Следовательно, решение задачи T(5,16)=21. Однако это не значит автоматически, что суммарная масса уносимых предметов равна 16. Действительно, T(1,16)=5, а соответствующая этой подзадаче суммарная масса предметов равна 4. Рассмотренная задача является широко известной задачей о рюкзаке.

T[0, 0]: = 0
 for j:= 1 to 16 do
 T[0, j] = 0;
 for i:=1 to 5 do
 T[i, 0]: = 0
 For  i:=1 to 5 do
     for j:=1 to 16 do
     if  j >= M[i] then
          T[i, j]: = max(T[i - 1, j], T[i - 1, j - M[i]] + C[i])
          else
           T[i, j] = T[i - 1, j]