Министерство образования и науки Российской Федерации. Государственное образовательное учреждение высшего профессионального образования «Вятский государственный гуманитарный университет»
ФАКУЛЬТЕТ ИНФОРМАТИКИ

Кафедра прикладной математики и информатики
КУРСОВАЯ РАБОТА

Методы решения задачи о рюкзаке
Выполнил студент 3 курса группы ПМ-31

Перевощиков Сергей Владимирович

Научный руководитель: к.п.н, доцент кафедры

прикладной математики и информатики

Разова Елена Владимировна
Киров 2010


Оглавление
Введение

Глава 1 Задача о загрузке, рюкзаке, ранце. Постановка и NP-полнота задачи

1.1 Постановка задачи о рюкзаке

1.2 NP – полнота задачи

Глава 2 Методы решения задачи о рюкзаке

2.1 Классификация методов

2.2 Динамическое программирование

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

2.4 Метод ветвей и границ

2.5 Жадный алгоритм

2.6 Сравнительный анализ методов

2.7 Модификации задачи

Заключение

Литература

Приложение 1

Приложение 2

Приложение 3

Приложение 4




Введение

Классическая задача о рюкзаке (о загрузке) известна очень давно, ниже приведена ее формализация. Пусть есть N разных предметов, каждый предмет имеет вес w_i и полезность p_i , так же имеется максимальный вес W, который можно положить в рюкзак. Требуется собрать такой набор предметов P, чтобы полезность их была наибольшей, а суммарный вес не превышал W.[6]. Конечно, никто не собирается писать программу, чтобы наилучшим образом загрузить рюкзак, отправляясь в поход или в путешествие, тут все слишком просто, и никто не задумывается об этом, но существует и более широкое применение.

Задача о загрузке (задача о рюкзаке) и различные её модификации широко применяются на практике в прикладной математике, криптографии, экономике, логистике, для нахождения решения оптимальной загрузки различных транспортных средств: самолетов, кораблей, железнодорожных вагонов и т.д.

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

1.        Каждый предмет можно брать только один раз.

2.        Каждый предмет можно брать сколько угодно раз.

3.        Каждый предмет можно брать определенное количество раз

4.        На размер рюкзака имеется несколько ограничений.

5.        Некоторые вещи имею больший приоритет, чем другие

Цель данной работы – выделить основные методы решения задачи о загрузке, классифицировать и сравнить эти методы.

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

Алгоритмы решения можно разделить на два типа: точные и приближенные. Точные: применение динамического программирования, полный перебор, метод ветвей и границ (сокращение полного перебора). Приближенные алгоритмы: Жадный алгоритм.




Глава 1 Задача о загрузке, рюкзаке, ранце. Постановка и NP-полнота задачи

Номер предмета (i)	Вес предмета (кг)	Цена (У.е)	Относительная цена (У.е/кг)
1	10	60	6
2	20	100	5
3	30	120	4

Заключение

В ходе исследования задачи о рюкзаке были выявлены три основных алгоритма решения. Полный перебор, ДП – программирование, жадный алгоритм. Так же был рассмотрен Метод ветвей и границ, но как сокращение полного перебора. Все методы разделены на две группы. Первая группа – точные методы, сюда входят ДП – алгоритмы, Полный перебор и Метод ветвей и границ. Вторая группа – приближенные методы, к таким методам относится Жадный алгоритм. Выбор использования того или иного метода спорный вопрос, все зависит от постановки задачи, а так же от того, какие цели поставлены. Если требуется найти точное решение, то конечно нужно использовать точные методы, при небольшом наборе входных данных (предметов до 10-20), подойдет перебор или метод ветвей и границ в силу простоты реализации, при больших, следует использовать ДП – алгоритм. Если же точность решения не так важна, или входные данные таковы, что ни один из точных методов не работоспособен, остается применять только приближенные алгоритмы. Но остается возможность комбинирования различных методов для ускорения, или даже применение каких либо “уловок” для конкретного примера. Надеяться же на построение полиномиального алгоритма нет смысла, так как данная задача NP-полна. Безусловно, данная задача очень важна с точки зрения ее приложения в реальной жизни. Не смотря на свою “древность”, рюкзак не только не забывается, наоборот, интерес к нему задаче растет. Оптимальная загрузка транспорта помогает сокращать расходы, получать большую прибыль. Также задача применяется в криптографии и прикладной математике.




Литература

1.       Вирт, Н. Алгоритмы и структуры данных [Текст] / Н. Вирт. – Пер. с англ.-М.Мир, 1989.-360 с., ил.

2.       Визгунов, Н.П. Динамическое программирование в экономических задачах с применением системы MATLAB [Текст] / Н.П. Визгунов. – Н.Новгород.: ННГУ, 2006. – 48 с.

3.       Кузюрин, Н.Н Сложность комбинаторных алгоритмов. Курс лекций [Текст] / Н.Н. Кузюрин, С.А.Фомин. – 2005. – 79 с.

4.       Гери, М. Вычислительные машины и труднорешаемые задачи [Текст] / М. Гери, Д. Джонсон. – М.: Мир, 1982 – 416 с.

5.       Окулов, С. М - Программирование в алгоритмах [Текст] / С.М. Окулов. – М.: БИНОМ. Лаборатория знаний, 2004. – 341 с.: ил.

6.       Окулов, С.М. Информатика в задачах [Текст] / С.М. Окулов, А.А, Пестов, О.А. Пестов. – Киров: Изд-во ВГПУ, 1998. — 343с.

7.       Царев, В.А. Проектирование, анализ и программная реализация структур данных и алгоритмов: Учебное пособие [Текст] / В.А. Царев, А.Ф. Дробанов. – Череповец., 2007. – 169 с.

8.       Акулич, И.Л Динамическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов [Текст] / И.Л. Акулич. – М.: Высш. шк., 1986. – 319 с., ил.

9.       Хаггари, Р. Дискретная математика для программистов [Текст] / Р. Хаггари. – М.: Техносфера, 2003. – 320с.

10.   Кормен, Т. Алгоритмы: построение и анализ [Текст] / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. — Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с.




Приложение 1

Автор задачи: С.М. Окулов

В ресторане собираются N посетителей. Посетитель с номером i, имеющий сумму денег Pi и полноту Si, подходит к двери ресторана во время Ti. Входная дверь ресторана имеет K состояний открытости. Состояние открытости двери может изменяться на одну единицу за единицу времени: дверь открывается на единицу или остается в том же состоянии. В начальный момент времени дверь закрыта (состояние 0). Посетитель с номером i входит в ресторан только в том случае, если дверь открыта специально для него, то есть когда состояние открытости двери совпадает с его степенью полноты Si. Если в момент прихода посетителя состояние двери не совпадает с его степенью полноты, то посетитель уходит и больше не возвращается.

Ресторан работает в течение времени T.

Требуется, правильно открывая и закрывая дверь, добиться того, чтобы за время работы ресторана в нем собрались посетители, общая сумма денег у которых максимальна.

Решение

Это классическая задача на метод динамического программирования. Состояния открытости двери можно представить “треугольной решеткой”, изображенной на рисунке. Каждая вершина определяет степень открытости q в момент времени t. Некоторым вершинам решетки приписаны веса, равные сумме денег у посетителя, приходящего в момент времени t и имеющего степень полноты, равную q. Требуется найти путь по решетке, проходящий через вершины, сумма весов которых имеет максимальное значение. Следует отметить, что нет необходимости хранить оценки всех вершин. Нам необходимо подсчитать оценки для момента времени t. Это возможно, если известны их значения для всех предыдущих моментов времени, однако для подсчета достаточно помнить только оценки для момента времени t–1. Приведем более простой пример входных данных:

3 5 6

3 4 1

5 10 1

1 4 1

Соответствующая решетка приведена на рисунке. Справа на рисунке указаны моменты времени. Слева от некоторых вершин решетки приведены суммы денег у посетителей, приходящих в этот момент времени и имеющих степень полноты, совпадающей со степенью открытости двери, записанной в вершине решетки. Ответ для данного примера очевиден: 11.

Основная процедура, остальные очевидны:

Procedure Solve;

Var i,j:Integer; {массивы для формирования оценок вершин решетки}

SOld,SNew:Array[0..MaxK] Of LongInt;

Begin

SOld[0]:=0;

For i:=1 To K Do SOld[i]:=-MaxLongInt;

SNew:=SOld;

For i:=1 To Tend Do Begin{цикл по моментам времени}

SNew[0]:=SOld[0];

For j:=1 To i Do{цикл по достижимым состояниям}

SNew[j]:=Max(SOld[j-1],SOld[j]);

{формирование оценок вершин}

For j:=1 To N Do {цикл по посетителям}

If (T[j]=i) And (SNew[S[j]]<>-MaxLongInt)

{если время прихода посетителя совпадает

с рассматриваемым моментом времени

и состояние достижимо, то изменяем

оценку вершины, соответствующей полноте

посетителя}

Then Inc(SNew[S[j]],P[j]);

SOld:=SNew;{запоминаем массив оценок}

End;

Res:=-MaxLongInt;

For i:=1 To K Do Res:=Max(Res,SNew[i]);

{находим максимальное значение

в окончательном массиве оценок}

End;


Приложение 2

Реализация метода ДП - программирования для задачи о рюкзаке:

program DP2;

{$APPTYPE CONSOLE}

uses SysUtils;

Const MaxW = 200; MaxN = 100;

var Value:array [0..MaxW,0..MaxN] of integer; {массив значений(сколько можно набрать для 1..W весов в 1..N предметов)}

Take :array [0..MaxW,0..MaxN] of boolean; {массив значений брали предмет или нет}

W,P :array [0..MaxN] of integer; {Массив весов, массив цен}

i, N, Weight, MaxWeight :integer;

procedure Init;

begin

assign(input,'input.txt');

reset(input);

readln(N, MaxWeight);

for i:=1 to N do readln(W[i], P[i]);

close(input);

end;

procedure Solve;

begin

fillchar(Take, sizeof(Take), false); {обнуляем}

fillchar(Value, sizeof(Value), 0);

for Weight:=1 to MaxWeight do begin {выбираем оптимум для веса Weight}

for i:=1 to N do {берем предметы с 1 по N}

{если вес предмета больше чем текущий вес рюкзака}

{или предыдущий набор дороже выбираемого}

if (W[i]> Weight) or (Value[Weight, i-1] >= Value[Weight-W[i], i-1]+P[i]) then begin

Value[Weight, i]:= Value[Weight, i - 1];

{тогдеа берем предыдущий набор}

Take[Weight, i]:= false; {говорим что вещь i не взята}

end

else begin {иначе добавляем к предыдущему набору текущий предмет}

Value[Weight, i]:= Value[Weight - W[i], i-1] +P[i];

Take[Weight, i]:= true; {говорим что вещь i взята}

end;

end;

end;

procedure Done;

begin

assign(output,'output.txt');

rewrite(output);

Writeln('Наилучший набор ', Value[MaxWeight, N]);

Weight:= MaxWeight;

for i:= N downto 1 do if Take[Weight, i] then begin

Write(i,' ');

Weight:= Weight-W[i];

end;

close(output);

end;

begin

Init;

Solve;

Done;

end.


Приложение 3

Реализация полного перебора для задачи о рюкзаке:

program FS;

{$APPTYPE CONSOLE}

uses SysUtils;

type mas = array[1..50] of integer;

Var N, MaxW:integer;{количество предметов, максимальный вес}

W,P,BestP,NowP:mas;

Max:Integer;

procedure Init;

var i:integer;

begin

assign(input,'input.txt');

reset(input);

readln(N, MaxW);

for i:=1 to N do readln(W[i], P[i]);

close(input);

end;

{передаем Nab - номер набранной группы, OstW-вместимость, stoim-цена набранного (еще не набрали нисколько)}

Procedure Search(Nab, OstW:integer; Stoim:integer);

var i:integer;

begin

{здесь OstW-вес который следует набрать из оставшихся. Stoim-стоимость текущего решения}

{Nab - набор предметов. если наполнили рюкзак

и набрали стоимость больше чем имеется, то считаем это новым решением}

if (Nab > N) and (Stoim > Max) then begin {найдено решение}

BestP:=NowP;

Max:=Stoim;

end

{иначе если количество взятых <= обьема. забиваем рюкзак дальше}

else if Nab<=N then {иначе если набрано меньше чем влазит}

for i:=0 to OstW div W[Nab] do begin {идем от 0 до ост. места}

NowP[Nab]:=i; {берем предмет Nab 0..OstW div W[Nab] раз}

Search(Nab+1,OstW-i*W[Nab],Stoim+i*P[Nab]);

{после каждого взятия предмета увеличиваем стоимость набора

и уменьшаем место в рюкзаке на вес предмета, так же увеличиваем

количество раз взятия предмета}

end;

end;

procedure print(name:string; out_:mas; num:integer);

var i:integer;

begin

if num=0 then begin

Writeln('Наилучший набор ', Max);

Writeln;

Write(' Номер предмета:');

for i:=1 to n do write(i: 3);

Writeln;

end else begin

Write(name);

for i:=1 to n do write(out_[i]: 3);

Writeln;

end;

end;

procedure Done;

begin

assign(output,'output.txt');

rewrite(output);

print('Наилучший набор ',bestP,0);

print(' Количество взятых:',BestP,1);

print(' Вес предмета:',W,1);

print('Стоимость предмета:',P,1);

close(output);

end;

begin

init;

Search(1, MaxW, 0);

done;

end.




Приложение 4

Реализация Жадного алгоритма для задачи о рюкзаке:

program Greedy;

{$APPTYPE CONSOLE}

uses SysUtils;

var W, P:array [1..15000] of integer; {веса, цены}

Price:array [1..15000] of real; {относительная ценность}

Take:array [1..15000] of boolean; {использование предметов}

i, N, BestPrice, NowWeight, MaxWeight:integer;

{Количество предметов, Лучшая стоимость, Текущий вес, Макс. вес}

{Считаем что предметы уже отсортированы}

procedure Init;

begin

assign(input,'input.txt');

reset(input);

readln(N, MaxWeight);

for i:=1 to N do readln(W[i], P[i]);

close(input);

end;

procedure Solve;

begin

fillchar(Take, sizeof(Take), False);

i:=0;

while NowWeight+W[i+1]<MaxWeight do begin

inc(i);

BestPrice:= BestPrice + P[i];

NowWeight:= NowWeight + W[i];

Take[i]:= true;

end;

end;

procedure Done;

begin

assign(output,'output.txt');

rewrite(output);

i:=1;

writeln('Максимальная стоимость ',BestPrice);

writeln('Вес предметов максимальной стоимости ',NowWeight);

writeln('Используемые предметы');

writeln('Вес Цена');

while Take[i] do begin

writeln(W[i],' ',P[i]);

inc(i);

end;

close(output);

end;

begin

init;

solve;

done;

end.