Задача о рюкзаке

Введение

Задача о одноразмерном рюкзаке считается классикой дискретной оптимизации. Эта задача и её модификации часто применяются при построении модели очень многих задач практики. Обобщённо задача формулируется следующим образом: из некоторого количества объектов, имеющих параметры «вес» и «стоимость», необходимо выбрать некоторое количество объектов так, чтобы в результате получить в сумме максимум стоимости и не превысить допустимый максимальный вес.

Если формулировать более строго, то:

1. Предполагаем, что Р(i) > 0 и W(i) > 0, где Р это стоимость, а W – это вес i-го объекта. А i= 1,…,N , где N– количество объектов.
2. Необходимо определить требуемый булевый вектор Х, имеющий размерность N, где X(i) = 1, в случае укладки i-того предмета в рюкзак, X(i) = 0, в случае не укладки i-того предмета в рюкзак, чтобы достигалась наибольшая сумма Σ P(i) Х(i) и было справедливо условие Σ W(i) Х(i) ≤ С, где С > 0 это ёмкость рюкзака.

Имеются разные примерные и уточнённые алгоритмы решения этой проблемы. К числу точных алгоритмов можно отнести:

1. Полный перебор.
2. Использование ветвей и границ.
3. Использование динамического программирования.

К приближённым алгоритмам относятся алгоритмы:

• жадности.
• генетики.

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

Решение задачи о рюкзаке

Предполагаем, что веса объектов это натуральные числа, а цена объектов — это вещественные числа.

INPUТ: // Вводная информация.

Массивы начальных данных состоят из целочисленных весов W и вещественных стоимостей P объектов W(1...N) > 0 и Р(1...N) > 0, где N число объектов и С > 0 – ёмкость рюкзака.

OUТРUТ: // Информация на выходе.

Булев массив Х(1...N), где Х(i) = 1, если i - тый объект попадает в рюкзак, и X(i) = 0, если i – тый объект не кладут в рюкзак.

STАRТ // запуск программы.

Шаг 1 // сортируем исходные данные.

Сортировка исходных данных выполняется по уменьшению номинальной цены объектов:

Р(1) / W(1) >= Р(2) / W(2) >= ...>= Р(i) / W(i)>=… >= Р( N) / W(N)

здесь P(i) > 0 цена объекта i , W(i) >0 весовая характеристика объекта i.

Массив Х(1...N) изначально состоит из нулевых компонентов.

Чтобы уменьшить используемый объём памяти при работе программы, задаётся минимум веса в комплексе исходных данных W_min = min( W ).

Шаг 2 // формирование необходимых массивов.

Формируем вещественный массив чисел LР, имеющий размерность (W_min… С) и целочисленный массив LСr, имеющий размерность (W_min… С) .

Записываем в LP и LCr параметры первого компонента из прошедшего сортировку списка исходных данных.

LР(W(1)) = Р(1)

LСr(W(1)) = 1

здесь Р(1) цена и W(1) весовой параметр первого компонента в прошедшем сортировку списке исходных данных.

Шаг 3 // наполнение текущих массивов.

FОR i = 2 ТО N // циклическая обработка остальных компонентов исходных данных.

Примем W(i) и P(i) весовой параметр и цена i-того элемента исходных данных.

Формируем массив с вещественными числами Сlоnе, который имеет размерность (W_min… С). Вводим в Сlоnе цену i-того элемента исходных данных.

Сlоnе (W(i)) = Р(i)

Выполняем копирование в Сlоnе отличные от нуля параметры из массива LР, добавив цену Р(i) действующего компонента и увеличив его индексацию на его весовой параметр W(i), если при этом индексация в Сlоnе не превысит объём рюкзака С.

FОR j = W_min ТО (С - W(i))

IF LР(j) >0 ТНЕN

Сlоnе (j + W(i)) = LР(j) + Р(i)

ЕND IF

NЕХТ // окончание циклической копии.

Выполняем преобразование массивов LР, LСr на базе информации массива Сlоnе и делаем обновление в массивах LР и LСr компонентов, цена которых в Сlоnе превышает стоимость в LР.

FОR j = W_min ТОС

IF Сlоnе (j) >0 АND Сlоnе (j) > LР(j) ТНЕN

LР (j) = Сlоnе (j)

LСr(j) = i

ЕND IF

NЕХТ // окончание циклического преобразования LР, LСr

NЕХТ // окончание цикличности по остальным компонентам

Шаг 4 // оформление итогов, движение в обратную сторону.

В LР вычисляем наибольший стоимостной показатель Рmах = МАХ(LР), это оптимальная цена. Индексный параметр определённого в массиве компонента равняется весу решения. Пусть он будет Wr, то есть LР(Wr) = Рmах. Запишем этот компонент в Х:

Х(LСr( Wr )) = 1

затем

// циклическое оформление итогов.

UNТIL Wr > 0 // если Wr = 0, то итоги оформлены.

// выполняем уменьшение веса решения на весовой параметр прибавленного в итоги объекта.

Wr = Wr - W(LСr( Wr ))

// Выполняем проверку на внесение очередного компонента в Х.

IF Х(LСr(Wr) = 0 thеn // нет

X(LCr(Wr)) = 1 // добавляем

ЕLSЕ // добавлен

Заканчиваем цикл UNТIL и выполняем повтор шагов 2 — 4, но на шаге 2 массивы LР, LСr не формируем, а просто обнуляем. Повторение шага один (выполнение сортировки исходных данных) делать нет необходимости. Фактически это рекурсивное действие, но поскольку уже выполнена начальная сортировка исходных данных, она не глубокая. При определённых комплектах исходных данных рекурсия вообще отсутствует.

При повторном проведении вычислений просматриваются лишь исходные данные, индексный параметр которых менее LСr(Wr), а также снижается необходимый объём рюкзака до уже набранного весового параметра Wr.

N_NЕW = LСr(W ) -1

С_NЕW = Wr

GОTО шаг 2

ЕND IF

NЕХТ // окончание циклического оформления итогов.

FINISН // окончание программы.

Стоимостной параметр будет равен Σ Р(i) Х(i), весовой параметр Σ W(i) Х(i). Доказать корректность вычислений цены рюкзака можно легко доказать с помощью индукции. Также без проблем можно восстановить оптимальный предметный комплект. Данный алгоритм даёт возможность выработать точное решение задачи о рюкзаке.

Обобщённая сложность этого алгоритма формируется из сложности сортировки исходных данных и осуществления третьего шага алгоритма (учитывая количество итераций). Временной интервал выполнения третьего шага пропорционален произведению количества объектов на объём рюкзака (N • С).