Задача об укладке рюкзака

Задача:

Задача о рюкзаке (англ. Knapsack problem) — дано [math]N[/math] предметов, [math]n_i[/math] предмет имеет массу [math] w_i gt 0[/math] и стоимость [math] p_i gt 0[/math] . Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины [math]W[/math] (вместимость рюкзака), а суммарная стоимость была максимальна.

Содержание

Формулировка задачи [ править ]

Дано [math]N[/math] предметов, [math]W[/math] — вместимость рюкзака, [math]w=<1>,w_<2>,dots,w_>[/math] — соответствующий ему набор положительных целых весов, [math]p=<1>,p_<2>,dots,p_>[/math] — соответствующий ему набор положительных целых стоимостей. Нужно найти набор бинарных величин [math]B=<1>,b_<2>,dots,b_>[/math] , где [math]b_ = 1 [/math] , если предмет [math]n_i[/math] включен в набор, [math] b_ = 0 [/math] , если предмет [math]n_i[/math] не включен, и такой что:

1. [math]b_ <1>w_<1>+ dots + b_ w_ leqslant W[/math]
2. [math]b_ <1>p_<1>+ dots + b_ p_ [/math] максимальна.

Варианты решения [ править ]

Задачу о рюкзаке можно решить несколькими способами:

Метод динамического программирования [ править ]

Пусть [math]A(k, s)[/math] есть максимальная стоимость предметов, которые можно уложить в рюкзак вместимости [math]s[/math] , если можно использовать только первые [math]k[/math] предметов, то есть [math][/math] , назовем этот набор допустимых предметов для [math]A(k,s)[/math] .

[math]A(k, 0) = 0[/math]

[math]A(0, s) = 0[/math]

Найдем [math]A(k, s)[/math] . Возможны 2 варианта:

1. Если предмет [math]k[/math] не попал в рюкзак. Тогда [math]A(k, s)[/math] равно максимальной стоимости рюкзака с такой же вместимостью и набором допустимых предметов [math]\>[/math] , то есть [math]A(k,s) = A(k-1, s)[/math]
2. Если [math]k[/math] попал в рюкзак. Тогда [math]A(k, s)[/math] равно максимальной стоимости рюкзака, где вес [math]s[/math] уменьшаем на вес [math]k[/math] -ого предмета и набор допустимых предметов [math]\>[/math] плюс стоимость [math]k[/math] , то есть [math]A(k-1, s-w_k) + p_k[/math]

[math] A(k, s) = egin A(k-1, s), & b_k = 0 \ A(k-1, s-w_k) + p_k, & b_k = 1 \ end [/math]

То есть: [math]A(k,s) = max(A(k-1,s), A(k-1,s-w_) + p_)[/math]

Стоимость искомого набора равна [math]A(N,W)[/math] , так как нужно найти максимальную стоимость рюкзака, где все предметы допустимы и вместимость рюкзака [math]W[/math] .

Восстановим набор предметов, входящих в рюкзак

Будем определять, входит ли [math]n_i[/math] предмет в искомый набор. Начинаем с элемента [math]A(i,w)[/math] , где [math]i = N[/math] , [math]w = W[/math] . Для этого сравниваем [math]A(i,w)[/math] со следующими значениями:

1. Максимальная стоимость рюкзака с такой же вместимостью и набором допустимых предметов [math]\>[/math] , то есть [math]A(i-1, w)[/math]
2. Максимальная стоимость рюкзака с вместимостью на [math]w_i[/math] меньше и набором допустимых предметов [math]\>[/math] плюс стоимость [math]p_i[/math] , то есть [math]A(i-1, w-w_i)+p_i[/math]

Заметим, что при построении [math]A[/math] мы выбирали максимум из этих значений и записывали в [math]A(i, w)[/math] . Тогда будем сравнивать [math]A(i, w)[/math] c [math]A(i-1, w)[/math] , если равны, тогда [math]n_i[/math] не входит в искомый набор, иначе входит.

Метод динамического программирование всё равно не позволяет решать задачу за полиномиальное время, потому что задача о ранце (или задача о рюкзаке) — одна из NP-полных задач комбинаторной оптимизации.

Реализация [ править ]

Сначала генерируем [math]A[/math] .

Затем найдем набор [math]ans[/math] предметов, входящих в рюкзак, рекурсивной функцией:

Сложность алгоритма [math]O(NW)[/math]

Пример [ править ]

[math]W = 13, N = 5[/math]

[math]w_ <1>= 3, p_ <1>= 1 [/math]

[math]w_ <2>= 4, p_ <2>= 6 [/math]

[math]w_ <3>= 5, p_ <3>= 4 [/math]

[math]w_ <4>= 8, p_ <4>= 7 [/math]

[math]w_ <5>= 9, p_ <5>= 6 [/math]

1	2	3	4	5	6	7	8	9	10	11	12	13
k = 0
k = 1			1	1	1	1	1	1	1	1	1	1	1
k = 2			1	6	6	6	7	7	7	7	7	7	7
k = 3			1	6	6	6	7	7	10	10	10	11	11
k = 4			1	6	6	6	7	7	10	10	10	13	13
k = 5			1	6	6	6	7	7	10	10	10	13	13

Числа от 0 до 13 в первой строчке обозначают вместимость рюкзака.

В первой строке как только вместимость рюкзака [math]n geqslant 3[/math] , добавляем в рюкзак 1 предмет.

Рассмотрим [math]k = 3[/math] , при каждом [math]s geqslant 5 ([/math] так как [math]w_3 = 5)[/math] сравниваем [math]A[k-1][s][/math] и [math]A[k-1][s-w_3]+p_3[/math] и записываем в [math]A[k][s][/math] стоимость либо рюкзака без третьего предмета, но с таким же весом, либо с третьим предметом, тогда стоимость равна стоимости третьего предмета плюс стоимость рюкзака с вместимостью на [math]w_3[/math] меньше.

Максимальная стоимость рюкзака находится в [math]A(5, 13)[/math] .

Восстановление набора предметов, из которых состоит максимально дорогой рюкзак.

Начиная с [math]A(5, 13)[/math] восстанавливаем ответ. Будем идти в обратном порядке по [math]k[/math] . Красным фоном обозначим наш путь

1	2	3	4	5	6	7	8	9	10	11	12	13
k = 0
k = 1			1	1	1	1	1	1	1	1	1	1	1
k = 2			1	6	6	6	7	7	7	7	7	7	7
k = 3			1	6	6	6	7	7	10	10	10	11	11
k = 4			1	6	6	6	7	7	10	10	10	13	13
k = 5			1	6	6	6	7	7	10	10	10	13	13

Таким образом, в набор входит [math]2[/math] и [math]4[/math] предмет.

Стоимость рюкзака: [math] 6 + 7 = 13[/math]

Вес рюкзака: [math] 4 + 8 = 12[/math]

Ограниченный рюкзак [ править ]

Задача:

Ограниченный рюкзак (англ. Bounded Knapsack Problem) — обобщение классической задачи, когда любой предмет может быть взят некоторое количество раз.

Формулировка Задачи [ править ]

Каждый предмет может быть выбран ограниченное [math]b_i[/math] число раз. Задача выбрать число [math]x_i[/math] предметов каждого типа так, чтобы

• максимизировать общую стоимость: [math]sum_^N p_ix_i[/math] ;

• выполнялось условие совместности: [math]sum_^N w_ix_i leqslant W[/math] ;

где [math] x_i in (0,1,dots,b_i)[/math] для всех [math] i= 1,2,dots,N[/math] .

Варианты решения [ править ]

При небольших [math]b_i[/math] решается сведением к классической задаче о рюкзаке. В иных случаях:

• Методом ветвей и границ.
• Методом динамического программирования.

Метод динамического программирования [ править ]

Пусть [math]d(i,c)[/math] максимальная стоимость любого возможного числа предметов типов от 1 до [math]i[/math] , суммарным весом до [math]c[/math] .

Заполним [math]d(0,c)[/math] нулями.

Тогда меняя i от 1 до [math]N[/math] , рассчитаем на каждом шаге [math]d(i,c)[/math] , для [math]c[/math] от 1 до [math]W[/math] , по рекуррентной формуле:

[math]d(i,c) = max(d(i – 1, c – lw_i) + lp_i) [/math] по всем целым [math] l [/math] из промежутка [math] 0 leqslant l leqslant min(b_i,lfloor c/w_i
floor)[/math] .

Если не нужно восстанавливать ответ, то можно использовать одномерный массив [math]d(c)[/math] вместо двумерного.

После выполнения в [math] d(N,W) [/math] будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

Реализация [ править ]

Сложность алгоритма [math]O(NW^2)[/math] .

Неограниченный рюкзак [ править ]

Задача:

Неограниченный рюкзак (англ.Unbounded Knapsack Problem) — обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.

Формулировка Задачи [ править ]

Каждый предмет может быть выбран любое число раз. Задача выбрать количество [math]x_i[/math] предметов каждого типа так, чтобы

• максимизировать общую стоимость: [math]sum_^N p_ix_i[/math] ;

• выполнялось условие совместности: [math]sum_^N w_ix_i leqslant W[/math] ;

где [math] x_i geqslant 0 [/math] целое, для всех [math] i= 1,2,dots,N[/math] .

Варианты решения [ править ]

Самые распространенные методы точного решения это:

• Метод ветвей и границ.
• Метод динамического программирования.

Метод динамического программирования [ править ]

Пусть [math]d(i,c)[/math] – максимальная стоимость любого количества вещей типов от 1 до [math]i[/math] , суммарным весом до [math]c[/math] включительно.

Заполним [math]d(0,c)[/math] нулями.

Тогда меняя i от 1 до [math]N[/math] , рассчитаем на каждом шаге [math]d(i,c)[/math] , для [math]c[/math] от 0 до [math]W[/math] , по рекуррентной формуле:

После выполнения в [math] d(N,W) [/math] будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

Если не нужно восстанавливать ответ, то можно использовать одномерный массив [math]d(c)[/math] вместо двумерного и использовать формулу:

[math] d(c) = max(d(c), d(c – w_i) + p_i) [/math] ;

Сложность алгоритма [math]O(NW)[/math] .

Непрерывный рюкзак [ править ]

Задача:

Непрерывный рюкзак (англ. Continuous knapsack problem) — вариант задачи, в котором возможно брать любую дробную часть от предмета, при этом удельная стоимость сохраняется.

Формулировка Задачи [ править ]

Задача выбрать часть [math]x_i[/math] каждого предмета так, чтобы

• максимизировать общую стоимость: [math]sum_^N p_ix_i[/math] ;

• выполнялось условие совместности: [math]sum_^N w_ix_i leqslant W[/math] ;

где [math] 0 leqslant x_i leqslant 1[/math] дробное, для всех [math] i= 1,2,dots,N[/math] .

Варианты решения [ править ]

Возможность брать любую часть от предмета сильно упрощает задачу. Жадный алгоритм дает оптимальное решение в данном случае.

Реализация [ править ]

Задача о суммах подмножеств [ править ]

Задача:

Задача о суммах подмножеств (англ. Subset sum problem, Value Independent Knapsack Problem) — задача из семейства, в которой стоимость предмета совпадает с его весом.

Формулировка Задачи [ править ]

Нужно выбрать подмножество так, чтобы сумма ближе всего к [math]W[/math] , но не превысила его. Формально, нужно найти набор бинарных величин [math]x_i[/math] , так чтобы

• максимизировать общую стоимость: [math]sum_^N w_ix_i[/math] ;

• выполнялось условие совместности: [math]sum_^N w_ix_i leqslant W[/math] ;

[math] x_j = 1 [/math] если [math] j[/math] предмет назначен рюкзаку, иначе [math] x_ = 0 [/math] , для всех [math] i= 1,2,dots,N[/math] .

Варианты решения [ править ]

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

• Метод динамического программирования.
• Гибридный метод на основе динамического программирования и поиска по дереву. В худшем случае, работает за [math] O(n) [/math] .

Метод динамического программирования [ править ]

Пусть [math]d(i,c)[/math] максимальная сумма [math]leqslant c[/math] , подмножества взятого из [math] 1, dots, i[/math] элементов.

Заполним [math]d(0,c)[/math] нулями.

Тогда меняя i от 1 до [math]N[/math] , рассчитаем на каждом шаге [math]d(i,c)[/math] , для [math]c[/math] от 0 до [math]W[/math] , по рекуррентной формуле:

После выполнения в [math] d(N,W) [/math] будет лежать максимальная сумма подмножества, не превышающая заданное значение.

Сложность алгоритма [math]O(NW)[/math] .

Задача о размене [ править ]

Задача:

Задача о размене (англ. Change-Making problem) — имеются [math] N [/math] неисчерпаемых типов предметов с весами [math]w_i[/math] . Нужно наполнить рюкзак предметами с суммарным весом [math]W[/math] .

Часто задачу ставят как, дать сдачу наименьшим количеством монет.

Формулировка Задачи [ править ]

Каждый предмет может быть выбран любое число раз. Задача выбрать количество [math]x_i[/math] предметов каждого типа так, чтобы

• минимизировать количество взятых предметов: [math]sum_^N x_i[/math] ;

• сумма весов выбранных предметов равнялась вместимости рюкзака: [math]sum_^N w_ix_i = W[/math] ;

Где [math] x_i geqslant 0 [/math] целое, для всех [math] i= 1,2,dots,N[/math] .

Варианты решения [ править ]

Самые распространенные методы точного решения это:

• Метод ветвей и границ.
• Метод динамического программирования.

Метод динамического программирования [ править ]

Пусть [math]d(i,c)[/math] минимальное число предметов, типов от 1 до [math]i[/math] , необходимое, чтобы заполнить рюкзак вместимостью [math]c[/math] .

Пусть [math]d(0,0) = 0[/math] , а [math]d(0,c) = inf[/math] для всех [math]c gt 0[/math] .

Тогда меняя i от 1 до [math]N[/math] , рассчитаем на каждом шаге [math]d(i,c)[/math] , для [math]c[/math] от 0 до [math]W[/math] , по рекуррентной формуле:

После выполнения в [math] d(N,W) [/math] будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

Если не нужно восстанавливать ответ, то можно использовать одномерный массив [math]d(c)[/math] вместо двумерного и использовать формулу:

[math] d(c) = min(d(c), d(c – w_i) + 1) qquad for c = w_i, dots, W[/math] .

Сложность алгоритма [math]O(NW)[/math] .

Задача об упаковке [ править ]

Задача:

Задача об упаковке (англ. Bin Packing Problem) — имеются [math] N [/math] рюкзаков вместимости [math] W [/math] и столько же предметов с весами [math]w_i[/math] . Нужно распределить все предметы, задействовав минимальное количество рюкзаков.

Формулировка Задачи [ править ]

Математически задачу можно представить так:

• минимизировать количество рюкзаков: [math]sum_^N y_i[/math] ;

• так чтобы выполнялось условие на совместность: [math]sum_^N w_ix_ leqslant Wy_j qquad j in <1, dots, N>[/math] ;

[math] x_ = 1 [/math] если [math] j[/math] предмет назначен [math]i [/math] рюкзаку. Иначе [math] x_ = 0 [/math] .

[math] y_i = 1 [/math] если [math] i[/math] рюкзак используется. Иначе [math] y_i = 0 [/math] .

Варианты решения [ править ]

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

Мультипликативный рюкзак [ править ]

Задача:

Мультипликативный рюкзак (англ. Multiple Knapsack Problem) — есть [math]N[/math] предметов и [math]M[/math] рюкзаков ( [math]Mleqslant N[/math] ). У каждого рюкзака своя вместимость [math]W_i[/math] . Задача: выбрать [math]M[/math] не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.

Формулировка Задачи [ править ]

Максимизировать [math]sum_^M sum_^ p_jx_[/math]

так, чтобы [math]sum_^N w_jx_ leqslant W_i[/math] выполнялось для всех [math] i= 1,2,dots,N[/math] .

[math]sum_^x_=1[/math] для всех [math] i= 1,2,dots,N[/math] .

[math] x_ = 1 [/math] если [math] j[/math] предмет назначен [math]i [/math] рюкзаку. Иначе [math] x_ = 0 [/math] .

Варианты решения [ править ]

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

Задача о назначении [ править ]

Задача:

Задача о назначении (англ. Generalized Assignment Problem) — Наиболее общая задача семейства. Отличается от мультипликативного рюкзака тем, что каждый предмет имеет различные характеристики в зависимости от рюкзака, куда его помещают. Есть [math]N[/math] предметов и [math]M[/math] рюкзаков ( [math]Mleqslant N[/math] ). У каждого рюкзака своя вместимость [math]W_i[/math] , у [math] j [/math] предмета [math] p_ [/math] стоимость и вес, при помещении его в [math] i [/math] рюкзак, равны [math] p_ [/math] и [math] w_ [/math] соответственно.

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

Формулировка Задачи [ править ]

Максимизировать стоимость выбранных предметов [math]sum_^Msum_^N p_ x_[/math] ,

при выполнении условия совместности [math]sum_^N w_ x_ leqslant W_i qquad i=1, ldots, M[/math] .

[math] sum_^M x_ leqslant 1 qquad j=1, ldots, N[/math] .

[math] x_ in <0,1>qquad i=1, ldots, N, quad j=1, ldots, N[/math] .

Варианты решения [ править ]

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

Многим известна так называемая задача об укладке рюкзака.
Вкратце напомню: из кучи предметов нужно выбрать такие, чтобы рюкзак был напихан под завязку и его еще можно было уволочь.
Говоря более формально, необходимо из данного набора 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 2 /a и по-прежнему отсортируем по d.

Отсортированный по d=b 2 /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 полной.

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

Одно из его первых упоминаний в книге Кереллера Nemhauser, Ullman, Discrete dynamic programming and capital allocation, Management Science, 15 p. 494-505, 1969.

Введение

Описание алгоритма решения задачи о рюкзаке с элементами псевдокода

INPUT: // Входные данные
Массивы исходных данных (ИД) содержат целые веса W и вещественные стоимости P предметов W(1. N) > 0 и P(1. N) > 0
где N число предметов и C > 0 – вместимость рюкзака.
OUTPUT: // Выходные данные
Булев массив X(1. N), где X(i) = 1, если предмет с номером i входит в решение, и X(i) = 0, если предмет с номером i не входит в решение.

START // начало алгоритма

Этап 1 // сортировка ИД
Сортируем ИД в порядке уменьшения удельной стоимости предметов:
P(1) / W(1) >= P(2) / W(2) >= . >= P(i) / W(i)>=… >= P( N) / W(N)
где P(i) > 0 стоимость предмета i , W(i) >0 вес предмета i.
В массиве X(1. N) все элементы первоначально = 0.
Для снижения потребности в памяти для алгоритма определяем минимальный вес в наборе ИД W_min = min( W )

Этап 2 // инициализация рабочих массивов
Создаем массив вещественных чисел LP размерностью (W_min… С)
и массив целых чисел LCr размерностью (W_min… С) . Заносим в массив LP и LCr данные первого элемента из отсортированного списка ИД
где P(1) стоимость и W(1) вес первого предмета в отсортированном списке ИД.

Этап 3 // заполнение рабочих массивов

Пусть W(i) и P(i) вес и стоимость текущего элемента ИД.
Создаем пустой массив вещественных чисел Clone размерностью (W_min… С).
Вносим в массив Clone стоимость текущего элемента ИД .
Копируем в массив Clone ненулевые данные из массива LP добавляя стоимость P(i) текущего элемента и увеличивая его индекс на его вес W(i), при условии что индекс в Clone не превзойдет вместимости рюкзака C.

Проводим модификацию массивов LP, LCr на основе данных массива Clone. Обновляем в массивах LP,LCr только те элементы стоимость которых в Clone больше чем в LP.

Этап 4 // формирование результата, обратный спуск
В массиве LP находим максимальное значение стоимости Pmax = MAX( LP ), это стоимость найденного оптимального решения. Индекс найденного в массиве элемента равен весу решения, обозначим его Wr, т.е. LP( Wr) = Pmax. Внесем первый найденный элемент в X:
далее

Выходим из цикла UNTIL и повторяем этапы 2, 3, 4 ( только на этапе 2 массивы LP, LCr не создаем, a заполняем нулями ). Повторять этап 1 (сортировка ИД) не нужно. Это по существу рекурсия, но из за предварительной сортировки ИД, она будет не глубокой. На некоторых наборах ИД рекурсии вообще может не быть. При повторе расчетов рассматриваем только те ИД, индекс которых меньше LCr( Wr ) и снижаем требуемый размер рюкзака до достигнутого веса Wr.

FINISH // конец алгоритма
Стоимость найденного решения Σ P(i) X(i), вес Σ W(i) X(i).
Правильность расчета итоговой стоимости рюкзака легко доказывается по индукции. Восстановление оптимального набора предметов, тоже не вызывает затруднений. Представленный алгоритм позволяет получить точное решение целочисленной задачи о рюкзаке.

Итоговые замечания

1. Общая сложность представленного алгоритма складывается из сложности сортировки ИД и сложности выполнения этапа 3 алгоритма (с учетом числа итераций). Время работы этапа 3 пропорционально числу предметов на вместимость рюкзака (N * C). Заранее определить число итераций достаточно сложно. Число итераций может варьироваться от до числа предметов в решении Σ X(i). При каждой итерации возникающей на этапе 4 объем вычислений на этапах 2, 3 уменьшается. Верхняя оценка временной сложности всего алгоритма не превышает N * C * ( число итераций + 1)
2. Потребность алгоритма в памяти пропорциональна вместимости рюкзака C и не зависит от числа предметов во входном наборе данных N, что выгодно отличает его от метода ДП.
3. Внутренние циклы этапа 3 легко выполняются параллельно.
4. При большом разбросе удельной стоимости предметов, если на этапе 3 алгоритма в верхней части массива LP перестают происходить изменения, можно прерывать этап 3 и не рассматривать оставшиеся предметы с низкой удельной стоимостью.
5. Если вместимость рюкзака С, достаточно велика, так что массивы размерности С не могут быть созданы по техническим причинам или веса предметов являются вещественными числами, то предложенный алгоритм может быть легко модифицирован заменой массивов связанными списками.
6. Является ли данный алгоритм полиномиальным или нет, я не берусь судить.