ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ - “ЗАДАЧА О РЮКЗАКЕ”

Алгоритмы, предназначенные для решения одного типа задач, а именно, задач, которые в той либо ином представлении особенно часто встречаются в различных ситуациях в теории алгоритмов и носят общее название - «задача о рюкзаке». Отчего это семейство задач так называется?

В общем, задачу, которую мы обсудим, имеет следующую формулировку: «мы имеем некоторое количество k слитков массой m и с фиксированной ценной p, а также мы имеем рюкзак, в котором мы желаем унести слитков, чтобы получить с этого максимально большую стоимость, но мы ограничены в переносимой массе рюкзака. Исходя из этого, мы можем взять самый дорогой из наборов слитков и, не глядя на все остальное, положить его в рюкзак – это пример жадного алгоритма.

Жадные алгоритмы – этот алгоритм делает на каждом шаге локально оптимальный, подразумевая, что завершительное решение также будет лучшее. Хотя это не всегда так работает, но для огромного числа алгоритмических задач жадные алгоритмы обеспечивают лучшее решение. Следует выделить, что вопрос о применимости жадного алгоритма для решения задач в каждом классе несет сугубо индивидуальный характер; но существует теория матроидов, доказывающая общее решение [3].

Матроиды

Когда возникает вопрос, какой жадный алгоритм эффективен или нет — что особенного в задаче, он дает точное решение. Оказалось, что уже есть математическая теория, которая может кое-что прояснить в ней. Это теория матроидов, фундамент которой был заложен Уитни в работе 1935 года.

Определение. Матроидом называется пара М=(Е, Ф), где Е - конечное непустое множество, Ф - семейство подмножеств множества Е, удовлетворяющее условиям:

(1) если X∈Ф и Y⊆X, то Y∈Ф;

(2)если X∈Ф, Y∈Ф и |X|<|Y|, то существует такой элемент a∈Y-X, что X ⋃(a)∈Ф [1].

Элементы множества E называются элементами матроидов, а множества из группы Ф называются независимыми от матроидов множествами. Самый большой инклюзивный набор независимых наборов называется матроидным базисом. Из аксиомы (2) видно, что все основания матроида состоят из одинакового числа элементов.Если Е - множество строк некоторой матрицы, а Ф состоит из всех линейно независимых множеств строк этой матрицы, то пара (Е, Ф) образует матроид, называемый матричным матроидом [1].

Другим важным типом матроидов является граф матроидов. Пусть G = (V, E) нормальный граф. Подмножество множества E называется ациклическим, если подграф, образованный ребрами этого подмножества, не содержит цикла, то есть лесом.

Теорема 1.  Если G = (V, E) нормальный граф, то является семейством всех ациклических подмножеств множества E.

M_G=(Е, Ф) является матроидом.

Доказательство. Аксиома (1) верна, потому что все подмножества ациклического множества явно ациклические. Докажем, что это верно (2). Пусть X и Y - два ациклических множества и |X|<|Y|. Допустим, что не существует такого ребра e∈Y, что множество X⋃{e} является ациклическим. Затем, когда одна из сторон добавляется из множества Y к множеству X, формируется цикл. Это означает, что конец каждого такого ребра принадлежит одному связному компоненту глобального подграфа, образованного ребрами Y. Но компоненты связности каждого из этих подграфов — деревья, а дерево с k вершинами содержит ровно k-1 ребер. Следовательно, в этом случае число ребер в Y не превосходило бы числа ребер в X, что противоречит условию |X|<|Y|.

Основой графовых матроидов являются все графовые фреймы. В случае связного графа это все его основные деревья.

Алгоритм Дейкстры

Алгоритм Дейкстры — это алгоритм, в котором поиск кратчайшего пути в графе жадный. Поскольку каждый шаг ищет вершину с наименьшим весом, он еще не обновляет значения других вершин. Кроме того, можно доказать, что кратчайший путь, найденный в вершине, является оптимальным.

Типичный пример жадного использования: Ваське выгодно делать самую «дорогую» работу, а самую дешевую вы не можете сделать — тогда ваш доход будет на максимуме. Возникает проблема: как распределить задание? Мы отсортируем задачи в порядке убывания стоимости и заполним график следующим образом: в том случае, если в расписании есть хотя бы еще одно незанятое место перед заказом, мы поместим его в последнее из данных мест. В противном случае мы не сможем выполнить его в срок, значит, поставим в конец из незанятых мест.

Получится следующий код:

//task – массив заданий

Arrays.soft (tasks); //сортируем по убыванию стоимости

TreeSet time = new TreeSet ();

for (int i = 1; i<= k; ++i) {time.add (i) ;}

int ans = 0;

for (int I = 0; I< k; ++i) {Integer tmp = time.floor (tasks[i].time);

if (tmp == null) {// если нет незанятого места в расписании, то в конце

time.remove (time.last ()) ;} else

{// иначе можно выполнить работу, добавляем в расписание

time.remove (tmp);

ans += tasks[i].cost;}}

Полный перебор.

Название технологии говорит само за себя. Для того чтобы получить решение, вам необходимо максимально реализовать все методы загрузки. Здесь мы рассмотрим постановку этой проблемы. Различные типы N предметов загружаются в рюкзак (количество предметов любого типа не ограничено), и любой предмет типа I имеет вес W i и стоимость P i, i = (1, 2 ... N). Необходимо определить максимальную стоимость груза, вес которого не превышает W. Простая рекурсивная реализация этого подхода очевидна. Временная сложность этого алгоритма составляет O (N!). Этот алгоритм очень сложен и может работать только с небольшими значениями N. По мере увеличения N число вариантов быстро увеличивается, а использование подхода полного перебора делает задачу практически неразрешимой. Первый элемент возможно выбрать четырьмя способами, второй — тремя, третий — двумя, и тогда мы можем взять только одну оставшуюся предКоличество предметов. Пускай Maxw - объем рюкзака, Pi - стоимость i-года предмета, Wi - вес i-го предмета [2].

(передаём Num - номер набранной группы, RedW-емкость, S-цена набранного (еще не набран))

Procedure Poisk(Num, W, S:integer);

Var i:integer;

Begin

{ResW- вес должен быть получен от остальных. S- стоимость текущего выбора}

{Num- Если набор предметов, упакованных с рюкзаками, имеет оценку выше стоимости, то это считается новым решением}

If (Num > N) and (S > Max) then begin {найдено решение}

BestP:=NowP;

Max:=s;

End

{В противном случае, если взятых<= объём, то кладём в рюкзак дальше}

Else if Num<= N then {в противном случае, если набрано меньше, чем помещается}

For i:=0 to ResW div W[Num] do begin {идём от 0 до ост. места}

NowP[Num]:=I; {берём Num пока помещается в ранец}

Poisk(Num+1,ResW-i*W[Num], S+i*P[Num]); {после каждого взятого предмета мы устанавливаем стоимость и уменьшаем место в рюкзаке по весу предмета, а также увеличиваем количество раз взятых предметов}

End;

Заключение

В ходе расследования проблемы с рюкзаком были выявлены некоторые основные алгоритмы решения. Полный перебор, алгоритм Дейкстры, алгоритм жадности. Вся техника разделена на две группы. Первая группа — это технология без ошибок, то есть технология полного перебора. Вторая группа приближений, в которую входит жадный алгоритм. Выбор применения тем или иным способом является проблемой, которая является спорным, это зависит от того, что цель, а также постановка задачи устанавливается. Конечно, если вам нужно найти безошибочное решение, вам нужно использовать безошибочный подход с использованием небольшого набора входных данных (до 10–20 элементов). Если точность решения не так важна или если входные данные таковы, что ни один из безошибочных методов не работает, остается применить только алгоритм приближения. Тем не менее, в некоторых случаях также можно комбинировать различные методы ускорения или использовать любой «трюк». Нет оснований полагаться на построение полиномиального алгоритма. Конечно, эта работа особенно важна с точки зрения реального использования. Несмотря на свою «старость», рюкзак не только не забыт, но, наоборот, к нему растет интерес. Самые высокие транспортные расходы снижают затраты и приносят большую прибыль. Эта проблема также применяется к криптографии и прикладной математике [2].

Список литературы:

1. НОУ ИНТУИТ https://www.intuit.ru/studies/courses/101/101/lecture/2966?page=2
2. Мир знаний http://mirznanii.com/a/115865/metody-resheniya-zadachi-o-ryukzake
3. Дискретная математика: Алгоритмы http://rain.ifmo.ru/cat/view.php/theory/algorithm-analysis/greedy-2004