Ответ

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).

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

Объяснение:

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

Потребность алгоритма в памяти пропорциональна вместимости рюкзака C и не зависит от числа предметов во входном наборе данных N, что выгодно отличает его от метода ДП.

Внутренние циклы этапа 3 легко выполняются параллельно.

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

Если вместимость рюкзака С, достаточно велика, так что массивы размерности С не могут быть созданы по техническим причинам или веса предметов являются вещественными числами, то предложенный алгоритм может быть легко модифицирован заменой массивов связанными списками