Pull to refresh

Алгоритм решения задачи о рюкзаке ( версия 2, исправленная)

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

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


Первая версия описания алгоритма было послана мною в институт математики им. С. Л. Соболева Сибирского отделения РАН, откуда был прислан ответ что указанный алгоритм известен давно. Цитирую:
Одно из его первых упоминаний в книге Кереллера Nemhauser, Ullman, Discrete dynamic programming and capital allocation, Management Science, 15 p. 494-505, 1969.
Тем не менее я решил ознакомить сообщество с алгоритмом, т.к. в известных мне учебниках по дискретной математике я его не обнаружил (возможно плохо искал). В первой версии алгоритма была ошибка, указанная мне пользователем wataru. За это ему большое спасибо. Я постарался эту ошибку устранить. До алгоритма я дошел самостоятельно, так что надеюсь ничьих прав не нарушаю. Возможно кому нибудь описание будет интересно и пригодится.

Введение


Задача о одномерном рюкзаке (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: // Выходные данные
Булев массив 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 данные первого элемента из отсортированного списка ИД
  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 // формирование результата, обратный спуск
В массиве LP находим максимальное значение стоимости Pmax = MAX( LP ), это стоимость найденного оптимального решения. Индекс найденного в массиве элемента равен весу решения, обозначим его Wr, т.е. LP( Wr) = Pmax. Внесем первый найденный элемент в X:
 X( LCr( Wr ) ) = 1 
далее
// цикл формирование результата 
UNTIL Wr > 0 // если Wr = 0, результат сформирован  
 // уменьшаем вес решения на вес добавленного в результат предмета
  Wr = Wr - W( LCr( Wr ) )   
  // Проверяем, не внесен ли уже следующий элемент в  X 
  IF  X(LCr( Wr ) = 0 then  // не внесен
       X( LCr( Wr ) ) = 1   //  вносим
  ELSE  //   внесен  

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

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

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


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


Литература

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

Articles