Динамическое программирование / Задача о рюкзаке

Задача о рюкзаке

Назначение. Онлайн-калькулятор предназначен для решения задачи о ранце методами динамического программирования (прямой и обратной прогонки). см. пример решения.

Здесь будет отображаться решение.

Инструкция. Выберите количество предметов для загрузки, нажмите Далее.

Скачать пример оформления

Задача о ранце

Имеются n предметов, которые необходимо поместить в рюкзак (ранец). Пусть известны вес a_j и «ценность» c_j каждого предмета (j= 1,2,... ,n). Требуется заполнить рюкзак, не превышая его грузоподъемности (объема) b и максимизируя суммарную ценность груза. Получаем следующую булеву ЗЦЛП (задача о рюкзаке):

Опишем алгоритм решения задачи о рюкзаке, основанный на методе динамического программирования. Пусть коэффициенты в удовлетворяют соотношениям:
c_j>0, a_j>0, b>0, c_j∈Z, a_j∈Z, b∈Z, (j=1,2,..,n)
Легко видеть, что тогда множество допустимых векторов задачи ограничено и не пусто (x₁ = x₂ = ... = x_n = 0).
Для каждого k∈{1,2,...,n} и y∈{1,2,...,b} рассмотрим вспомогательную задачу о рюкзаке

оптимальное значение целевой функции которой обозначим f_k(y). Заметим, что f_n(b) равно искомому оптимальному значению целевой функции исходной задачи (81). Ниже мы получим рекуррентные соотношения, выражающие значение функции f_k(y) через ее значения при меньших k и y. На основе этих соотношений можно организовать процесс, позволяющий для всех k и y найти f_k(y), в том числе fn(b). В этом заключается основная идея метода.
Рассмотрим задачу (105) при k = 1. В ней требуется разместить в рюкзак грузоподъемности y максимальное число предметов первого типа. Очевидно, что

f₁(y)=c₁·[y/a₁] (y=1,2,...,b)

Рассмотрим теперь задачу (105) при k > 1. Требуется разместить в рюкзак предметы первых k типов, так, чтобы суммарная ценность груза была бы максимальна. Предположим, что рюкзак заполнен оптимально.
Если в рюкзаке нет ни одного предмета k-го типа, то он заполнен только предметами типов 1,2,... ,k - 1. Так как заполнение оптимально, то значение целевой функции (суммарная ценность) в этом случае равна f_k(y) = f_k_-1(y).
Если в рюкзаке предмет k-го типа находится только в одном экземпляре, то оставшееся место y — a_k должно быть заполнено оптимальным образом предметами типов 1,2,... ,k — 1. В этом случае f_k(y) = f_k_-1(y - a_k) + c_k.
Если в рюкзаке два предмета k-го типа, то под остальные предметы остается место равное y - 2a_k. Так как заполнение оптимально, то
f_k(y) = f_k_-1(y-2a_k) + 2c_k.
Эти рассуждения можно провести далее, рассмотрев случаи с тремя, четырьмя и т. д. предметами k-го типа, находящимися в рюкзаке, вплоть до случая, когда в рюкзаке находится максимально возможное число [y/a_k] предметов k-го типа. Оставшееся место y - a_k · [y/a_k] должно быть заполнено оптимальным образом предметами первых (k - 1) типов. Получаем
f_k(y) = f_k_-1(y - a_k · [y/a_k]) + c_k · [y/a_k].
Подводя итог вышесказанному, можно сделать вывод, что

Упростим рекуррентное соотношение (107). Для этого вначале вместо y в него подставим y - a_k. Получим

f_k(y-a_k) = max{f_k-1(y-a_k),...,f_k-1(y-a_k·[y/a_k])+c_k·[y/a_k]-c_k}

Теперь ясно, что в соотношении (107) все элементы, среди которых ищется максимальный, кроме первого, можно заменить на f_k(y - a_k) + c_k, т. е.

f_k(y) = max{f_k-1(y), f_k(y-a_k)+c_k} (k=2,...,n; y=a_k+1,...,b) (108)

Вычисления проводятся по формулам (106) и (108) (при y < 0 положим f_k(y) = -∞). Удобно использовать таблицу F размера n x b. В k-ой строке и y-ом столбце этой таблицы записывается значение f_k(y). Таблица заполняется по строкам сверху вниз, в каждой строке слева направо. Заметим, что для вычисления f_k(y) достаточно знать f_k-₁(y) и f_k(y - a_k). Это позволяет хранить только одну строку таблицы F.
Для того, чтобы кроме оптимального значения целевой функции найти компоненты решения, используют другую таблицу I. Таблица I также имеет размеры n x b и заполняется следующим образом. В k-ой строке и y-ом столбце этой таблицы записывается максимальной номер i(k,y) ненулевой компоненты оптимального вектора задачи (105), т. е.

Примеры

Пример №1 решения задачи о рюкзаке.
Задание. В рюкзак объема V = 7 кладут N = 5 предметов.Объемы, веса и количество предметов в каждой группе приведены в таблице.

Объем	1	2	3	1	1
Вес	2	3	2	4	1
Кол-во	1	3	3	1	2

Максимизировать общий вес рюкзака.

Решение. I этап. Условная оптимизация.
f₁(L) = max(2x₁); 0 < x₁ < 1; x₁ = 0,1.
f₁(0) = max[0*2] = 0
f₁(1) = max[0*2, 1*2] = 2
f₁(2) = max[0*2, 1*2] = 2
f₁(3) = max[0*2, 1*2] = 2
f₁(4) = max[0*2, 1*2] = 2
f₁(5) = max[0*2, 1*2] = 2
f₁(6) = max[0*2, 1*2] = 2
f₁(7) = max[0*2, 1*2] = 2
Таблица 1 – Расчет значения функции f₁(L)

L	1	2	3	4	5	6	7
f₁(L)	2	2	2	2	2	2	2
x₁	1	1	1	1	1	1	1

f₂(L) = max[3x₂ + f₁(L - 2x₂)]; 0 < x₂ < 3; x₂ = 0,1,2,3.
f₂(0) = max[0*3+0] = 0
f₂(1) = max[0*3+2] = 2
f₂(2) = max[0*3+2, 1*3+0] = 3
f₂(3) = max[0*3+2, 1*3+2] = 5
f₂(4) = max[0*3+2, 1*3+2, 2*3+0] = 6
f₂(5) = max[0*3+2, 1*3+2, 2*3+2] = 8
f₂(6) = max[0*3+2, 1*3+2, 2*3+2, 3*3+0] = 9
f₂(7) = max[0*3+2, 1*3+2, 2*3+2, 3*3+2] = 11
Таблица 2 – Расчет значения функции f₂(L)

L	1	2	3	4	5	6	7
f₂(L)	2	3	5	6	8	9	11
x₂	0	1	1	2	2	3	3

f₃(L) = max[2x₃ + f₂(L - 3x₃)]; 0 < x₃ < 3; x₃ = 0,1,2,3.
f₃(0) = max[0*2+0] = 0
f₃(1) = max[0*2+2] = 2
f₃(2) = max[0*2+3] = 3
f₃(3) = max[0*2+5, 1*2+0] = 5
f₃(4) = max[0*2+6, 1*2+2] = 6
f₃(5) = max[0*2+8, 1*2+3] = 8
f₃(6) = max[0*2+9, 1*2+5, 2*2+0] = 9
f₃(7) = max[0*2+11, 1*2+6, 2*2+2] = 11
Таблица 3 – Расчет значения функции f₃(L)

L	1	2	3	4	5	6	7
f₃(L)	2	3	5	6	8	9	11
x₃	0	0	0	0	0	0	0

f₄(L) = max[4x₄ + f₃(L - 1x₄)]; 0 < x₄ < 1; x₄ = 0,1.
f₄(0) = max[0*4+0] = 0
f₄(1) = max[0*4+2, 1*4+0] = 4
f₄(2) = max[0*4+3, 1*4+2] = 6
f₄(3) = max[0*4+5, 1*4+3] = 7
f₄(4) = max[0*4+6, 1*4+5] = 9
f₄(5) = max[0*4+8, 1*4+6] = 10
f₄(6) = max[0*4+9, 1*4+8] = 12
f₄(7) = max[0*4+11, 1*4+9] = 13
Таблица 4 – Расчет значения функции f₄(L)

L	1	2	3	4	5	6	7
f₄(L)	4	6	7	9	10	12	13
x₄	1	1	1	1	1	1	1

f₅(L) = max[1x₅ + f₄(L - 1x₅)]; 0 < x₅ < 2; x₅ = 0,1,2.
f₅(0) = max[0*1+0] = 0
f₅(1) = max[0*1+4, 1*1+0] = 4
f₅(2) = max[0*1+6, 1*1+4, 2*1+0] = 6
f₅(3) = max[0*1+7, 1*1+6, 2*1+4] = 7
f₅(4) = max[0*1+9, 1*1+7, 2*1+6] = 9
f₅(5) = max[0*1+10, 1*1+9, 2*1+7] = 10
f₅(6) = max[0*1+12, 1*1+10, 2*1+9] = 12
f₅(7) = max[0*1+13, 1*1+12, 2*1+10] = 13
Таблица 5 – Расчет значения функции f₅(L)

L	1	2	3	4	5	6	7
f₅(L)	4	6	7	9	10	12	13
x₅	0	0	0	0	0	0	0

II этап. Безусловная оптимизация.
Таким образом, максимальный вес рюкзака f₅(7) равна 13 кг.
При этом x₅ = 0, так как f₅(7) = 13 достигается при х₅=0 (см. таблицу 5).
Предметы остальных типов распределяются следующим образом:
L = 7 - 1 * 0 = 7
f₄(7) = 13 достигается при х₄ = 1 (см. таблицу 4).
L = 7 - 1 * 1 = 6
f₃(6) = 9 достигается при х₃ = 0 (см. таблицу 3).
L = 6 - 3 * 0 = 6
f₂(6) = 9 достигается при х₂ = 3 (см. таблицу 2).
L = 6 - 2 * 3 = 0
f₁(0) = 0 достигается при х₁ = 0 (см. таблицу 1).
L = 0 - 1 * 0 = 0
В итоге наилучший вариант загрузки рюкзака достигается при значениях: x₁ = 0, x₂ = 3, x₃ = 0, x₄ = 1, x₅ = 0

Пример №2. Решим задачу
max(8x₁+5x₂+x₃)
3x₁+2x₂+x₃≤13
x∈Z, x≥0 (j=1,2,3)
методом динамического программирования.
По формулам (106) и (108) вычислим элементы таблицы F:

Оптимальное значение целевой функции ЗЦЛП равно f₃(13) = 34. По формулам (109) вычислим:

Для восстановления компонент решения в таблице I найдем
i(3,13)=2
i(3,13-a₂)=i(3,11)=2
i(3,11-a₂)=i(3,9)=1
i(3,9-a₁)=i(3,6)=1
i(3,6-a₁)=i(3,6)=1
Таким образом, оптимальный вектор имеет компоненты x₁ = 3, x₂ = 2, x₃ =0.

Задача о целочисленном рюкзаке

Имеется транспортное средство грузоподъемностью L. Требуется заполнить его грузом, состоящим из предметов различных типов, чтобы стоимость всего груза оказалась максимальной.
Для этого введем соответствующие обозначения:
W_i– вес одного предмета i-го типа;
P_i– стоимость одного предметаi-го типа;
x_i – число предметов i-го типа, загружаемых на имеющееся транспортное средство.
Необходимо подобрать груз максимальной ценности с учетом грузоподъемности транспортного средства L.
Математически формализовать данную экстремальную задачу можно следующим образом:

max ϕ (x) = max \sum_{i = 1}^{n} x_{i} P_{i} - стоимость груза

(1)

при ограничениях:

\sum_{i = 1}^{n} x_{i} W_{i} \leq L

x_i =0,1,... (т.е. предметы груза неделимы).
Решение задачи разбивается на n этапов, на каждом их которых определяется максимальная стоимость груза, состоящего из предметов первого типа (первый этап), первого и второго типов (второй этап)
и т.д. Для этого воспользуемся рекуррентным соотношением или критерием оптимальности Беллмана:
f_n (L) = max [ x_nP_n + f_n_-1(L-x_nW_n)], (2)
0<x_n< [L/W_n],
где f_n(L) – максимальная стоимость груза, состоящего из предметов n-го типа;
x_nP_n – стоимость взятых предметов n-го типа;
f_n_-1(L-x_nW_n) – максимальная стоимость груза, состоящего из предметов (n-1) типа с общим весом не более L-x_nW_n;
[L/W_n] – наибольшее целое число, не превосходящее L/W_n.
Будем считать f₀(L) = 0 для любого L. Последовательно найдя значение функции f₁(L), f₂(L), ..., f_n(L), можно получить полное решение сформулированной задачи.
Вывод:

каждый предмет имеется в неограниченном числе экземпляров;
требуется максимизировать суммарную ценность груза, не превышая грузоподъемности.

Пример №1.
Пусть:
W₁ = 4, W₂ = 3, W₃ = 2, W₄ = 1 (единиц груза);
P₁ = 28, P₂= 20,P₃ = 13, P₄ = 6 (денежных единиц);
L = 10 (единиц груза).
Найдем последовательно значения функций: f₁(L), f₂(L), f₃(L), f₄(L) при различных значениях L (0<L<10).

Решение данной задачи представлено в таблицах 1–4.
f₁(L) = max ( 28x₁); 0<x₁< [10/4]; x₁ =0, 1, 2.
Таблица 1 – Расчет значения функции f₁(L )

L	0-3	4-7	8-10
f₁(L)	0	28	56
x₁	0	1	2

f₂(L) = max [ x₂^.20 + f₁(L-x₂^.3)]; 0<x₂< [10/3]; x₂ =0, 1, 2,3.
Таблица 2 – Расчет значения функции f₂(L)

L	0-2	3	4-5	6	7	8	9	10
f₂(L)	0	20	28	40	48	56	60	68
x₂	0	1	0	2	1	0	3	2

f₃(L) = max [ x₃^.13 + f₂(L-x₃^.2)]; 0<x₃< [10/2]; x₃ =0, 1, 2,3,4,5.
Таблица 3 – Расчет значения функции f₃(L)

L	0-1	2	3	4	5	6	7	8	9	10
f₃(L)	0	13	20	28	33	41	48	56	61	69
x₃	0	1	0	0	1	1	0	0	1	1

f₄(L) = max [ x₄^.6 + f₃(L-x₄^.1)]; 0<x₄< [10/1]; x₄ =0, 1, 2, …,10.
Таблица 4 – Расчет значения функции f₄(L)

L	1	2	3	4	5	6	7	8	9	10
f₄(L)	6	13	20	28	34	41	48	56	62	69
x₄	1	0	0	0	1	0	0	0	1	0

Таким образом, максимальная стоимость груза f₄(10) равна 69 денежным единицам, при этом предметы четвертого типа загружать не следует, так как f₄(10) = 69 достигается при х₄=0 (см. таблицу 10).
Предметы остальных типов распределяются следующим образом:
х₃= 1, так как f₃(10) = 69 достигается при х₃= 1 (см. таблицу 9), следовательно, вес этого предмета равен двум единицам груза, поэтому остальные предметы можно загрузить лишь в пределах веса, равного
10-2=8 единицам груза;
f₂(8) = 56 достигается при х₂= 0 (см. таблицу 8), следовательно, предметы второго типа брать не следует;
f₁(8) = 56 достигается при х₁= 2 (см. таблицу 7), следовательно, предметов первого типа следует взять два.
В итоге наилучший вариант загрузки транспортного средства достигается при значениях х₁= 2; х₂= 0; х₃= 1; х₄= 0 (берутся два предмета первого типа и один – третьего типа).

Пример №2. Самолет загружается предметами N различных типов (табл. 1) с весом w_j и стоимостью c_j, j = 1,n. Максимальная грузоподъемность равна W=5. Определить максимальную стоимость груза, вес которого не более W.
Таблица 1 - Исходные данные

Тип j	Вес _wj	Стоимость _cj
1	2	65
2	3	80
3	1	30

Решение. Сделаем математическую постановку. Пусть _xj – количество предметов j-го типа, загружаемых в самолет. Тогда математическая модель имеет вид:

(1)

(2)
_{xj ≥ 0} (3)
_xj – целые. (4)

Отличительными особенностями задачи динамического программирования будут:
1. Этап j связан с загрузкой предметов j-го типа в количестве _xj единиц (_xj – управляемая переменная);
2. Состояние загружаемого самолета _Sj на этапе j определяется через ограничение (2) математической модели (1) –(4). В алгоритме прямой прогонки состояния ; 0 ≤ S_j ≤ W; S_n = W
В алгоритме обратной прогонки
3. Цель управления на этапе z_j = c_j_xj.
4. Варианты решения _xj этапа j описываются количеством предметов типа j: _xj_{= 0,1,…, [}_W_/_wj_]– целые.

Решим задачу методом обратной прогонки, загружая предметы с последнего типа (используя калькулятор).
Пусть F_j(S_j) – значение целевой функции (максимальная стоимость предметов, включенных на этапах _j_,_j_=1,..,_n при заданном состоянии системы _Sj

Рекуррентное соотношение для процедур обратной прогонки:

Этап 1.
_{F3(S3) = max{}_c3x3_};
_{x3 = 0,1,..,5};
_{S3 = 0,1,…,5};
_{S3 ≥ 1x3}.

_S3	_c3x3						opt
	_x3=0	_x3=1	_x3=2	_x3=3	_x3=4	_x3=5	_F3*(S3)	_x3*
0	0	–	–	–	–	–	0	0
1	0	30	–	–	–	–	30	1
2	0	30	60	–	–	–	60	2
3	0	30	60	90	–	–	90	3
4	0	30	60	90	120	–	120	4
5	0	30	60	90	120	150	150	5

Этап 2. F₂(S₂) = max{c₂x₂ + F₃(S₂– w₂x₂)}
x₂ = 0,1
S₂ = 0,1,..,5
S₂ ≥ 2x₂

_S2		c₂x₂ + F₃(S₂– w₂x₂)				_opt
		_x2=0		_x2=1		_F2*(S2)		_x2*
0		0 + 0 = 0		–		0		0
1		0 +30 = 30		–		30		0
2		0 + 60 = 60		–		60		0
3		0 + 90 = 90		80 + 0 = 80		90		0
	4		0 + 120 = 120		80 + 30 = 110		120		0
	5		0 + 150 = 150		80 + 60 = 140		150		0

Значение условного оптимума F₃(S₃) берется из предыдущей таблицы.
Этап 3. F₁(S₁) = max{c₁x₁ + F₂(S₁– w₁x₁)};
x₁ = 0,1,2;
_S1=5.

_S1	c₁x₁ + F₂(S₁– w₁x₁)			_opt
	_x1=0	_x1=1	_x1=2	_F1*(S1)	_x1*
5	0 + 150 = 150	65 + 90 = 155	130 + 30 +160	160	2

Определение управляемых переменных начинается с последней таблицы (обратный ход):
x1* = 2 → S1 = 2*2 = 4
S₂ = 5-4 =1 → x₂ = 0 → S₃ = 1 – 0 = 1 → x₃ = 1
Оптимальное решение X^* = (2,0,1)

Пример №2. Имеется склад, на котором присутствует некоторый ассортимент товаров. Запас каждого товара неограничен. У каждого товара своя стоимость Ci и масса mi. Методом динамического программирования сформировать такой набор товаров, чтобы его суммарная масса не превышала заданную грузоподъемность М, и стоимость была бы максимальной.

Пример №3. На станок для обработки в течение цикла V = 4 мин. могут загружаться заготовки трех типов. В таблице1 содержатся исходные данные о суммарной продолжительности обработки заготовок i-го типа и их стоимости pi (i = 1, 2, 3). Ка-кими типами заготовок необходимо загрузить станок, чтобы суммарная стоимость обработанных деталей была максимальна?

Задача о рюкзаке

Задача о ранце

Примеры

Задача о целочисленном рюкзаке

Правила ввода данных

Поиск

Поиск через Яндекс

Процесс

Сообщение

Условия предоставления оформления отчета в Word

Условия подписки