Задача о рюкзаке методом ДП Опции

[BCW]

Привет всем. Совсем потерял и покой и сон.
Никак не могу сделать эту задачу. Задача называется -задача о рюкзаке на паскале методом динамического программирования. Смысл: Есть рюкзак заданного размера например 70, есть 4 предмета которые имеют свой вес и стоимость. Необходимо забить рюкзак предметами чтобы общий вес их вмещался в рюкзак а стоимость при этом была наибольшей. т.е как бы из кучи разных вариантов выбрать оптимальный. но тем не мение выводит на экран все наборы т.е ход мыслей программы нужно отобразить. нашел несколько кодов но не один толком не работает. Вот к примеру такой:

Код

program rukzak_perebor;
const maxn=20;{?}
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
read(n);
read(w);
for i:=1 to n do read(weight[i]);
for i:=1 to n do read(price[i]);
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);
end.

Не работает совсем. В чем дело понять не могу. чуствую дело скоро дойдет до глюкозы
Помогите пожалуйста.
.

[Krjuger]

Ну не изуродовал,он просто ее так криво скопировал,а что не работает действительно не понятно,задача 1 в 1 с той что тебе надо и задача делает именно то,что от нее и требуеца.
Т
ебе не нравица,что ты руками должен вводить?Или тебе надо выводить промежуточные результаты?И что за знак вопроса около описания константы?если тебе непонятно зачем это,то почитай ,как реализуется массив в паскале.

[BCW]

Ну не изуродовал,он просто ее так криво скопировал,а что не работает действительно не понятно,задача 1 в 1 с той что тебе надо и задача делает именно то,что от нее и требуеца.
Т
ебе не нравица,что ты руками должен вводить?Или тебе надо выводить промежуточные результаты?И что за знак вопроса около описания константы?если тебе непонятно зачем это,то почитай ,как реализуется массив в паскале.

Да я ничего сам честно говоря не уродовал. А именно скопировал если покопать могу сказать где.
Вот программа которая лежит по ссылке я немного добавил "дружественный интерфейс" а то немного запутался с черным экраном.

Код

program rukzak_perebor;
const maxn = 20;
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 the number of items: ');
    read(n);
writeln('Enter the total weight: ');    
    read(w);
    for i:=1 to n do begin
writeln('Enter the', i, 'element weight: ');
    read(weight[i]);
    end;
    for i:=1 to n do begin read(price[i]);
    writeln('Enter the', i, 'element price: ');
    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);
end.

А как сделать её ДП? Что необходимо добавить?

Тебе не нравица,что ты руками должен вводить?Или тебе надо выводить промежуточные результаты?И что за знак вопроса около описания константы?если тебе непонятно зачем это,то почитай ,как реализуется массив в паскале.

Нет. Мне все подходит. Да мне нужно чтоб выводились промежуточные вычисления. Знак вопроса скопировал вместе с кодом - он не из вашего FAQ я не помню где достал.
Помогите доработать под нужды а?



Сообщение отредактировано: BCW - 22.06.2009 18:23