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

[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]

Не совершай моих ошибок,не путай динамическое програмирование и динамические структуры.насчет массива,который будет хранить промежуточные значения..,если ты возьмеш массив равный количеству возможных комбинаций,то ты не прогадаеш))),другое дело что для уже 10 вещей,паскаль не позволит создать массив,чтобы хранить все комбинации.Насчет ДП было конкретно сказано,что ты свою задачу разбиваеш на подзадачи.Вот тебе вариант подзадачи,просто найти комбинацию,которая влазит в твой мешок.Затем береш функцию,которая посчитает сумарную стоимость этих вещей,затем процедуту,которая будет проверять,есть ли данная стоимость в массиве результатов,и если нету,то записывать в массив.В итоге основная программа будет просто выбирать из твоего массива наибольшее число.
Я не совсем уверен,что это ДП,да и некоторые действия можно обьеденить в одну процедуру например.В общем это лиш идея того,как можно реализовать.

Т.е получается рекурсию нужно убрать? А на что заменить?

Например, для рюкзака можно написать такую рекурсию:

Код

function f(m, w)
если f еще не была посчитана
   считаем и запоминаем
возвращаем

А можно просто выбрать такой порядок обхода, чтобы мы всегда обращались к уже посчитанным значениям. В нашем случае это будет обход слева-направо, сверху вниз:

Код

for m
  for w
    f:=...

Плохо ты читал,видно надо еще пару раз прочитать и переосознать.

Сообщение отредактировано: Krjuger - 23.06.2009 16:09