Немного об укладке рюкзака

Многим известна так называемая задача об укладке рюкзака.
Вкратце напомню: из кучи предметов нужно выбрать такие, чтобы рюкзак был напихан под завязку и его еще можно было уволочь.
Говоря более формально, необходимо из данного набора A пар чисел a(i)b(i), выбрать такие, чтобы сумма чисел а не превосходила наперед заданного S, а сумма чисел b была максимальной. Σa(n) ≤ S, Σb(n)=max.

Исходный набор:

											Σ
a	3	14	25	26	32	2	28	23	1	9	163
b	11	12	5	30	31	25	19	27	32	33	225

В последней колонке указан суммарный вес Σa всех предметов и их суммарная стоимость Σb. Задаваемое S (грузоподъемность) не должна превышать Σa, иначе решение тривиально — мы можем унести все. Учитывая эти ограничения, с помощью суммарной стоимости Σb мы можем оценить, насколько суммарная стоимость полученного решения отличается от абсолютного максимума.

Существует несколько способов решения данной задачи, они описаны в Википедии.
Нам интересен "жадный" алгоритм.
Он заключается в вычислении для каждой пары ценности d=a/b, по которой пары сортируются и затем отбираются.

Набор с указанием ценности d:

											Σ
a	3	14	25	26	32	2	28	23	1	9	163
b	11	12	5	30	31	25	19	27	32	33	225
d	3,67	0,86	0,2	1,15	0,97	12,5	0,68	1,17	32,0	3,67

Отсортированный по d набор

											Σ
a	1	2	3	9	23	26	32	14	28	25	163
b	32	25	11	33	27	30	31	12	19	5	225
d	32,0	12,5	3,67	3,67	1,17	1,15	0,97	0,86	0,68	0,20

Попробуем найти решение при S=60.

											Σ
a	1	2	3	9	23	26	32	14	28	25	163
b	32	25	11	33	27	30	31	12	19	5	225
d	32,0	12,5	3,67	3,67	1,17	1,15	0,97	0,86	0,68	0,20

Первые пять предметов дадут нам Σa=38, Σb=128. Следующий предмет не помещается. С ним Σa=64.
Дыра, оставшаяся после укладки первых пяти предметов получилась размером: 60-38=22. Если просмотреть набор до конца, находится еще один предмет, который в эту дыру помещается.

											Σ
a	1	2	3	9	23	26	32	14	28	25	163
b	32	25	11	33	27	30	31	12	19	5	225
d	32,0	12,5	3,67	3,67	1,17	1,15	0,97	0,86	0,68	0,20

Итого: Σa=52, Σb=140.

К сожалению, это не является оптимальным решением.

Если мы заменим предмет 23-27 на 26-30,

											Σ
a	1	2	3	9	23	26	32	14	28	25	163
b	32	25	11	33	27	30	31	12	19	5	225
d	32,0	12,5	3,67	3,67	1,17	1,15	0,97	0,86	0,68	0,20

то Σa=55, Σb=143, что уже является оптимальным решением.

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

Вместо простого отношения d=b/a, возьмем d=b²/a и по-прежнему отсортируем по d.

Отсортированный по d=b²/a набор

											Σ
a	1	2	9	3	26	23	32	14	28	25	163
b	32	25	33	11	30	27	31	12	19	5	225
d	1024	312,5	121	40,33	34,6	31,7	30,0	10,3	12,9	1,0

 Для того же S=60

											Σ
a	1	2	9	3	26	23	32	14	28	25	163
b	32	25	33	11	30	27	31	12	19	5	225
d	1024	312,5	121	40,33	34,6	31,7	30,0	10,3	12,9	1,0

Σa=55, Σb=143. Мы сразу приходим к оптимальному решению.

Таким образом задача укладки рюкзака решается за линейное время и не является NP полной.