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

Причина побудившая автора к публикации

Описание алгоритма было послано мною в институт математики им. С. Л. Соболева Сибирского отделения РАН, откуда был прислан ответ что указанный алгоритм известен давно. Цитирую:

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

Риторический вопрос почему в учебниках по дискретной математике этого алгоритма нет, остался без ответа. Обоснование того, что алгоритм не является полиномиальным я не понял. До алгоритма я дошел самостоятельно, так что надеюсь ничьих прав не нарушаю. Возможно кому нибудь описание будет интересно и пригодится.

Введение

Задача о одномерном рюкзаке (0-1 knapsack) является классической задачей дискретной оптимизации [1],[2]. Данная задача и ее варианты широко используются для моделирования большого числа практических задач. В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.

Более точно, пусть P(i) > 0 и W(i) > 0 – соответственно стоимость и вес i-го предмета, где i = 1,2,3,…,N , а N– число предметов.

Требуется найти такой булев вектор X размерностью N, где
X(i) = 1, если предмет с номером i положен в рюкзак;
X(i) = 0, если предмет с номером i не положен в рюкзак;
чтобы была максимальной сумма Σ P(i) X(i)
и выполнялось неравенство Σ W(i) X(i) ≤ C, где C > 0 – вместимость рюкзака.

Существуют различные точные и приближенные алгоритмы решения задачи о рюкзаке.

К точным алгоритмам относятся:

• полный перебор
• метод ветвей и границ
• динамического программирования (ДП)

.

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

Рассмотрим вариант алгоритма решения задачи о рюкзаке при условии, что веса предметов являются натуральными числами, а стоимости предметов являются вещественными числами.

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

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

OUTPUT: // Выходные данные
Массив S содержит индексы элементов ИД составляющих оптимальное решение задачи о рюкзаке.
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.

Для снижения потребности в памяти для алгоритма определяем минимальный вес в наборе ИД W_min = min( W )

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

  LP( W(1) )  = P(1)   LCr( W(1) ) = 1 

где P(1) стоимость и W(1) вес первого предмета в отсортированном списке ИД.

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

 FOR i = 2 TO N  // цикл по оставшимся элементам ИД  

Пусть W(i) и P(i) вес и стоимость текущего элемента ИД.

Создаем пустой массив вещественных чисел Clone размерностью (W_min… С).
Вносим в массив Clone стоимость текущего элемента ИД

Clone( W(i) ) = P(i)

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

FOR j = W_min TO ( C - W(i) )     IF LP(j) >0 THEN     Clone( j + W(i) ) = LP(j) + P(i)    END IF NEXT // конец цикла копирования 

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

  FOR j = W_min TO C       IF Clone( j ) >0 AND Clone( j ) > LP( j ) THEN        LP( j ) = Clone( j )         LCr( j ) = i      END IF    NEXT  // конец цикла модификации LP, LCr  

NEXT  // конец цикла по оставшимся элементам 

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

// цикл формирование результата  UNTIL Wr > 0 // если Wr = 0, результат сформирован    LCr( Wr ) --> S   // заносим индекс ИД в результат   // уменьшаем вес решения на вес добавленного в результат предмета   Wr = Wr - W( LCr( Wr ) )   NEXT // конец цикла формирование результата 

FINISH // конец алгоритма

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

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

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

Литература

1. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность. М.: Мир, 1985.
2. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы: построение и анализ. М.: Издательский дом «Вильямc», 2005.