Название задача о рюкзаке возникает в следующей гипотетической ситуации

Название задача о рюкзаке возникает в следующей гипотетической ситуации. Представим туриста, который хочет взять с собой в путешествие рюкзак определенной весовой вместимости. Чтобы его заполнить, он может воспользоваться набором предметов заданного веса и ценности. Он может взять предметы, общий вес которых  не превышает вместимости рюкзака и хочет, чтобы их суммарная ценность была максимальной.

Постановка задачи

       Предполагается, что вместимость рюкзака известна и равна G кг, и для каждого типа i= предметов заданы вес qi и ценность ci. Не умоляя общности можно считать, что z1<z2<…<zm. Рассматриваемый вопрос об оптимальной загрузке рюкзака сводится к решению следующей задачи.

Задача. При заданных величинах G, qi, ci, i= требуется максимизировать функцию

на множестве векторов

x = (x1, x2, …, xm),

с целочисленными неотрицательными компонентами, удовлетворяющими условию

Обзор и анализ методов решения Основные процедуры метода ДП

Рассмотрим W аналогичных задач 

={ │ 0, целые, ,} - множество допустимых векторов.

При  множества содержат единственный нулевой вектор,

причем для всех таких z.

При справедливы рекуррентные соотношения:

  (9)

1 этап (прямой ход).

Для всех по формуле (9) последовательно вычисляют

и фиксируют индексы i(z), на которых достигаются максимумы в (9) (если максимум достигается на нескольких индексах, в качестве i(z) берется любой).

Процесс вычисления удобно представлять в виде табл. 2.

			…	W
			… …

Таблица 2 (информация в  таблице - динамическая шкала)

В конце табл. 2  находится искомое значение функции и  номер предмета

, на котором оно достигнуто.

2 этап (обратный  ход).

Определяется искомый вектор

, >0, целые, , при котором

.

В комплектуемый оптимальный набор в первую очередь включается предмет с номером: 

Далее вычисляем:

Если , то процесс заканчивается, иначе в указанный набор включается предмет с номером .

Комплектование набора заканчивается на некотором шаге j, на котором .

Пример решения  Исходные данные:

=15 – вместимость рюкзака. Данные о предметах в табл.3. 

	1	2	3
	3	4	5
	12	20	15

Таблица 3

Решение

Определим величину==3;

Прямой ход

, если , что означает – ценность рюкзака, вместимость которого , равна нулю.

Пусть . Найдем .

Неравенству удовлетворяет только предмет 1-го вида, т. к. =3 

=  максимум достигается на 1-м предмете, значит =1.