"Задача о рюкзаке" (перебор вариантов)

← →
Dter (2006-06-01 20:48) [0]

Пожалуйста, помогите изменить код так, чтобы находилась не максимальная стоимость, а минимальная!

procedure solve(k,w,st: integer);
var i: integer;
begin
writeln(st);
if (k>n) and (st>maxPrice) then
begin
best:=now; maxprice:=st;
end
else if k<=n then
for i:=0 to w div weigth[k] do
begin
now[k]:=i;
solve(k+1,w-i*weigth[k],st+i*price[k]);
end;
end;
begin
Assign(input,infile); reset(input);
Assign(output,outfile); rewrite(output);
read(w,n);
for i:=1 to n do read(price[i],weigth[i]);
solve(1,w,0);
writeln(maxprice);
end.

Сама задача (для тех кто не знает).
В рюкзак нагружаются различные предметы различной стоимости. Нужно найти максимальную стоимость груза, вес которого равен w.Заранее благодарен!

← →
Rial © (2006-06-01 21:13) [1]

Мне не очень понятно (точно и не очень хочется), что происходит.

Отсортируй массив пар стоимость - вес по возрастаию отношения
стоимость/вес.

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

вот элементарное (не оптимизированное) решение:

Const MyW=XX;//Заданный вес

Type TElement=record
W,P:Signle;
end;

ptElement=^TElement;

Var List:TList;

procedure Compare(Item1,Item2:Pointer):Integer;
Var D1,D2:Signle;
begin
With ptElement(Item1)^ do
D1:=P/W;
With ptElement(Item2)^ do
D2:=P/W;
If (D1>D2)then Result:=1 else
Result:=-1;
//Сравнение на совпадение действительных чисел,
//как правило, глупое занятие, поэтому опустим его.
end;

Var ptE:ptElement;
I,N:Integer;
fW,fP:Single;
begin
List:=TList.Create;
Try
Assign(input,infile); reset(input);
Assign(output,outfile); rewrite(output);
read(w,n);
for i:=1 to n do begin
New(ptE);
With ptE^ do
read(p,w);
List.Add(ptE);
end;
List.Sort;
//Ищем мин. цену
fP:=0.0;
fW:=MyW;
for i:=0 to n-1 do
With ptElement(List.Item[I])^ do
if (fW-W>0.0)then begin
fW:=fW-W;
fP:=fP+P;
end;
writeln(fP);
Finally
List.Free;
end;
end;

Писал прямо на форуме, так что могут быть мелкие опецатки.

← →
Cash © (2006-06-01 22:32) [2]

Это же задача о грабителе. (ее еще так называют)
Там смотри, в Solve стоит условие выбора максимальной стоимости.
Т. е. if (k>n) and (st>maxPrice) then... , а для выбора минимального
соответственно меняем на if (k>n) and (st<maxPrice) then ...

>чтобы находилась не максимальная стоимость, а минимальная!
Это очень просто - ничего не берем ;)
Или берем один предмет минимальной стоимости, проходящий по весу :)

Иначе нужно полностью переформулировать условие, чтобы оно имело смысл.

"Задача о рюкзаке" (перебор вариантов) Найти похожие ветки