Методы решения задачи о рюкзаке (стр. 3 из 4)
Диаграмма 1
2.7 Модификации задачи
1. Необходимо вывести только максимальную стоимость, набор нас не интересует.
2. В результате работы нужно получить не только максимальную стоимость, но и сам набор.
3. На размер рюкзака несколько ограничений (многомерность задачи).
4. Каждый предмет можно брать только лишь один раз.
5. Предметы можно брать произвольное количество раз.
6. Количество раз помещения предмета в рюкзак фиксировано. Либо для каждого предмета свое, либо для всех предметов одно.
7. Некоторые предметы должны обязательно быть уложены в рюкзак (имеют приоритет).
8. Находить несколько оптимальных решений (одинаковой стоимости, но с разным содержимым).
В ходе исследования задачи о рюкзаке были выявлены три основных алгоритма решения. Полный перебор, ДП – программирование, жадный алгоритм. Так же был рассмотрен Метод ветвей и границ, но как сокращение полного перебора. Все методы разделены на две группы. Первая группа – точные методы, сюда входят ДП – алгоритмы, Полный перебор и Метод ветвей и границ. Вторая группа – приближенные методы, к таким методам относится Жадный алгоритм. Выбор использования того или иного метода спорный вопрос, все зависит от постановки задачи, а так же от того, какие цели поставлены. Если требуется найти точное решение, то конечно нужно использовать точные методы, при небольшом наборе входных данных (предметов до 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 с.
Автор задачи: С.М. Окулов
В ресторане собираются 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.
Основная процедура, остальные очевидны:
ProcedureSolve;
Vari,j:Integer; {массивы для формирования оценок вершин решетки}
SOld,SNew:Array[0..MaxK] OfLongInt;
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]);
{формирование оценок вершин}
Forj:=1 ToNDo {цикл по посетителям}
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;
Реализация метода ДП - программирования для задачи о рюкзаке:
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.
Реализация полного перебора для задачи о рюкзаке:
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');