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

Введение

Задача о рюкзаке или ранце представляет собой проблему, касающуюся комбинаторной оптимизации: при задавании набора элементов, каждый из которых имеет собственный вес и значение, определяется точное количество каждого элемента, включаемого в подборку, так, чтобы общий вес был меньше или равен заданному пределу, и общее значение было бы настолько большим, насколько это возможно.
Она получила свое название от вопроса, с которым сталкивается любой человек, который ограничен одним ранцем очень маленького размера, куда ему предстоит поместить только самые ценные предметы.
Эта проблема часто может возникнуть при распределении ресурсов там, где существуют финансовые ограничения, и изучается в таких областях, как комбинаторика, информатика, теория множеств, криптография, прикладная математика и игровое программирование.
Проблема рюкзака известна уже более века, а ранние работы по этой теме датируются еще 1897 годом. Название «проблема рюкзака» было впервые найдено в ранних работах математика Тобиаса Данцига (1884-1956) и брало начало от банальной проблемы – упаковки самых ценных и полезных предметов в ограниченное пространство чемодана, не перегружая свой багаж.
Проблемы с «рюкзаками» возникают в реальных процессах принятия решений в самых разнообразных областях, таких как поиск наименее расточительного способа сокращения сырьевых ресурсов, выбор инвестиций и портфелей, выбор активов для секьюритизации своих средств, генерации ключей для ранцевых криптосистем.
Одним из ранних применений ранцевых алгоритмов было построение и оценка тестов, в которых у тестировщиков есть выбор, на какие вопросы они отвечают.
Например, если экзамен содержит 12 вопросов, каждый из которых стоит 10 баллов, тестировщик должен ответить только на 10 вопросов, чтобы достичь максимально возможного балла в 100 баллов.
Однако в тестах с неоднородным распределением точечных значений, т.е. за разные вопросы можно получить не одинаковое количество балов или в нашем случае точечных ценностей - труднее сделать выбор. Feuerman и Weiss предложили систему, в которой учащимся дают гетерогенный тест с общим количеством 125 возможных баллов. Студентов просят ответить на все вопросы в меру своих возможностей.
Из возможных подмножеств задач, суммарные значения которых составляют 100, алгоритм рюкзака определяет, какое подмножество дает каждому учащемуся максимально возможную оценку.
Предположим, мы планируем поход. И поэтому мы заинтересованы в заполнении ранца деталями, которые считаются самыми необходимыми для поездки.
Существует N различных типов предметов, которые считаются желательными.
Это могут быть: бутылка воды, яблоко, апельсин, сэндвич и т.д.
Каждый тип элемента имеет заданный набор из двух атрибутов, а именно: вес (или объем) и значение, определяющее уровень важности, связанный с каждой единицей этого типа элемента

.
Поскольку рюкзак имеет ограниченный вес (или объем), проблема состоит в том, чтобы выяснить, как загрузить ранцевую сумку с комбинацией единиц указанных типов предметов, которая дает наибольшую общую стоимость.
1. Возможные решения задачи
В рамках задачи о рюкзаке можно получить огромное количество проблем с распределением ресурсов.
Общая идея состоит в том, чтобы подумать о способности рюкзака, как доступного объемного ресурса, а типам предметов придать функцию действия, которым может быть выделен этот ресурс.
Сформулируем в голове два возможных случая, чтобы проиллюстрировать задачу о ранце в реальной жизни – например, это может быть распределение рекламного бюджета для продвижения отдельных продуктов какой-нибудь компании и/или распределение усилий по подготовке выпускных экзаменов по различным предметам.
Формально предположим, что нам заданы следующие параметры:
wk
 = вес каждого элемента типа k, для k = 1, 2, ..., N,
rk = значение, связанное с каждым элементом типа k,
для k = 1, 2, …, N.
c = весовая вместимость ранца.


Тогда наша задача может быть сформулирована так:

Где x1, x2, ..., xN - неотрицательные целочисленные переменные решения, определяемые xk = количество элементов типа k, загружаемых в рюкзак.
Нужно обратить внимание на то, что поскольку переменные xk являются целочисленными, то мы имеем не обычную линейную программу, а целую программу.
Следовательно, алгоритм Симплекс (Симплекс-метод) нельзя применить для решения этой проблемы.
В качестве простого численного примера предположим, что мы имеем: N = 3; w1 = 3, w2 = 8 и w3 = 5; r1 = 4, r2 = 6 и r3 = 5 и, наконец, c = 8. Наблюдая за этими тремя типами переменных мы увидим, что первый тип имеет наибольшее значение на единицу веса. То есть, из всех трех соотношений,
r1w1=43, r2w2=68, и r3w3=55
первое соотношение является наибольшим.
Поэтому кажется естественным попытаться загрузить в рюкзак как можно больше предметов типа 1.
Так как емкость рюкзака равна 8, такая попытка приведет к загрузке комбинации x1 = 2, x2 = 0 и x3 = 0, при этом общее значение равняется формуле, которая приводится ниже:
Является ли эта комбинация загрузки оптимальной? Данная комбинация составляет остаток в рюкзаке, что вызовет неудобства.
Действительно, оказывается, что эта комбинация не оптимальна. И что оптимальная комбинация состоит в том, чтобы
x1 = 1, x2 = 0 и x3 = 1 достигали общего значения 9.
Опишем, как получить оптимальное решение этой задачи с помощью динамического программирования. Как и в предыдущем нашем решении проблемы замены оборудования, процедура решения будет проходить поэтапно.

Этапы и состояния

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