Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [Pascal] Помогите с задачей о рюкзаке

Автор: BCworm 19.5.2009, 14:44

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

Код


program knapsack;
uses crt;

const maxn=40;
var n,w:integer;
weight,price:array[1..maxn]of integer;
best,now:array[1..maxn]of integer;
maxprice:longint;

procedure init;
var i:integer;
begin
writeln('Enter number of items: ');
read(n);
writeln('Enter some W: ');
read(w);
for i:=1 to n do begin
writeln('Enter weight ',i,' element');
read(weight[i]);
writeln('Enter price ',i,' element');
read(price[i]);
end;
end;

procedure rec(k,w:integer;st:longint);
var i:integer;
begin
if (k>n) and (st>maxprice) then
begin
best:=now;
maxprice:=st;
end else
if k<=n then
for i:=0 to w div weight[k] do
begin
now[k]:=i;
rec(k+1,w-i*weight[k],st+i*price[k]);
end;
end;

begin
init;
rec(1,w,0);
writeln(' ',maxprice);
writeln('press..');
readkey;
end.

Насколько я понял он выводит только стоимость набора. А мне нужно чтоб показывало ход вычислений т.е на каждом витке цикла выводился собраный набор предметов. Например 1 - 3 -5 вес 32 стоимость 466.

Может у кого есть что нибудь лучше? именно на паскале.

Помогите а?