Алгоритм решения задачи о рюкзаке в черновиках Из песочницы
Ниже алгоритм точного решения целочисленной задачи о рюкзаке. Предлагаемый алгоритм требует меньше вычислительных ресурсов и возможно проще алгоритма динамического программирования (ДП).
Причина побудившая автора к публикации
Описание алгоритма было послано мною в институт математики им. С. Л. Соболева Сибирского отделения РАН, откуда был прислан ответ что указанный алгоритм известен давно. Цитирую:
Одно из его первых упоминаний в книге Кереллера 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 // конец алгоритма
Представленный алгоритм позволяет получить точное решение целочисленной задачи о рюкзаке.
Итоговые замечания
- Общая сложность представленного алгоритма складывается из сложности сортировки ИД и сложности выполнения этапа 3 алгоритма. Время работы этапа 3 пропорциональна числу предметов в ИД и вместимости рюкзака ( N * C). Сложность и время работы алгоритма не зависят от стоимости предметов в наборе ИД .
- Потребность алгоритма в памяти пропорциональна вместимости рюкзака C и не зависит от числа предметов во входном наборе данных N, что выгодно отличает его от метода ДП.
- Внутренние циклы этапа 3 легко выполняются параллельно.
- При большом разбросе удельной стоимости предметов, если на этапе 3 алгоритма в верхней части массива LP перестают происходить изменения, можно прерывать этап 3 и не рассматривать оставшиеся предметы с низкой удельной стоимостью.
- Если вместимость рюкзака С, достаточно велика, так что массивы размерности С не могут быть созданы по техническим причинам или веса предметов являются вещественными числами, то предложенный алгоритм может быть легко модифицирован, использованием вместо массивов связанных списков.
- Является ли данный алгоритм полиномиальным или нет, я не берусь судить.
Литература
- Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность. М.: Мир, 1985.
- Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы: построение и анализ. М.: Издательский дом «Вильямc», 2005.
комментарии (25)