IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Задача о рюкзаке методом ДП
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 4
Пол: Мужской

Репутация: -  0  +


Привет всем. Совсем потерял и покой и сон.
Никак не могу сделать эту задачу. Задача называется -задача о рюкзаке на паскале методом динамического программирования. Смысл: Есть рюкзак заданного размера например 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.




Не работает совсем. В чем дело понять не могу. чуствую дело скоро дойдет до глюкозы
Помогите пожалуйста.
.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Решение есть вот тут: Переборные Алгоритмы
Только без ДП


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Стоп. Так это же ты прогу из нашего FAQ'а изуродовал до неузнаваемости!
Цитата(BCW @ 22.06.2009 10:28) *
Не работает совсем. В чем дело понять не могу.
Все работает. Дело, думаю, не программе.
И если ты выдвигаешь такие серьезные обвинения - будь добр, подтверди фактами.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Профи
****

Группа: Пользователи
Сообщений: 652
Пол: Мужской
Реальное имя: Алексей

Репутация: -  20  +


Ну не изуродовал,он просто ее так криво скопировал,а что не работает действительно не понятно,задача 1 в 1 с той что тебе надо и задача делает именно то,что от нее и требуеца.
Т
ебе не нравица,что ты руками должен вводить?Или тебе надо выводить промежуточные результаты?И что за знак вопроса около описания константы?если тебе непонятно зачем это,то почитай ,как реализуется массив в паскале.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5





Группа: Пользователи
Сообщений: 4
Пол: Мужской

Репутация: -  0  +


Цитата(Krjuger @ 22.06.2009 13:34) *

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


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

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 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Профи
****

Группа: Пользователи
Сообщений: 652
Пол: Мужской
Реальное имя: Алексей

Репутация: -  20  +


Эм,извини но я не понимаю,тебе промежуточные результаты или вычисления?во вторых,тут тоже есть фак
Динамические массивы и матрицы
Цитата

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

к несчастью не добавить, а переделать.

Сообщение отредактировано: Krjuger -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Krjuger @ 22.06.2009 19:56) *
Krjuger, ты путаешь. Динамическое программирование - это не динамическая память.

BCW, а ты способен вообще искать по Форуму? Вот, наприме, тема непосредственно на нужный тебе предмет:
Динамическое программирование

И я по-прежнему жду от тебя сведений о том, КАК именно не работает та программа, которую ты привел. Напиши, плз, что ты ей задаешь и что она выдает на это.



--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Профи
****

Группа: Пользователи
Сообщений: 652
Пол: Мужской
Реальное имя: Алексей

Репутация: -  20  +


LapДа работает та программа,может быть не совсем дружелюбно,но работает.Мда, а с разделами я действительно попутал.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9





Группа: Пользователи
Сообщений: 4
Пол: Мужской

Репутация: -  0  +


Цитата(Krjuger @ 23.06.2009 12:18) *

LapДа работает та программа,может быть не совсем дружелюбно,но работает.Мда, а с разделами я действительно попутал.


Да Lapp работает по крайней мере та что я скопировал из FAQ однозначно работает.
Спасибо за ссылки почитал.
Если я правильно понял необходимо завести массив в котором нужно сохранять результаты вызова функции. Так? Но какого размера он должен быть? Вариантов же может быть ого го го как!
Т.е получается рекурсию нужно убрать? А на что заменить?
..Чем дальше в лем тем толще партизаны! sad.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Профи
****

Группа: Пользователи
Сообщений: 652
Пол: Мужской
Реальное имя: Алексей

Репутация: -  20  +


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

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

Цитата

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

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

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

for m
  for w
    f:=...


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

Сообщение отредактировано: Krjuger -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 18:57
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name