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

> Динамическое программирование
сообщение
Сообщение #1


Гость






Вечер добрый.
Поставлена такая задача которую надо решить с помощью таблиц и динамического программирования предположительно. Пираты попали на остров, у них есть лодка которая может перевезти 100 кг, они нашли сокровища (различные) каждое из которых имеет свой вес и ценность, надо переветси такие сокровища, чтобы они имели максимальную ценность и общий вес их был <=100 кг (вместимость лодки).
Заранне благодарю
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2


Гость






Задача о рюкзаке в чистом виде smile.gif

Переборные алгоритмы
(решение на Паскале)

Дальше справишься, или нужна помощь?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


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

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

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


Цитата(Алена @ 14.11.2006 3:54) *
Задача о рюкзаке в чистом виде smile.gif

- это верно, но вот как быть с упомянутым динамическим программированием (ДП)? Я для себя как-то не вполне могу уяснить, насколько в данном случае рекурсия соответствует ДП..
Классически, сдедовало бы рассмотреть цикл по параметру, двоичное представление которого занимает n бит:
0010101110
- в этом примере из 10 предметов выбраны 3-й, 5-й, 7-й, 8-й и 9-й. Полный перебор по таким числам (от 0000000000 до 1111111111, то есть от 0 до 2^n-1) даст все возможные комбинации предметов, и из них можно выбрать максимальный вес, не превышающий заданного. При этом если делать честное суммирование для каждой комбинации, то уйдет много времени. Согласно принципу ДП, нужно сохранять результаты, полученные на предыдущих шагах. Например, если нужно выяснить вес комбинации
0010011101,
то можно воспользоваться тем, что мы уже знаем вес комбинации
0000011101,
и просто прибавить к ней вес 3-его предмета.
Таким образом, нам нужен, грубо говоря, массив весов комбинаций, занумерованных в порядке этого двоичного параметра, то есть массив размером 2^n.
ДП использует много памяти, но экономит время расчета. При больших n экономия довольно значительная, но и память нужна немалая.. Рекурсия же делает нечто подобное, как я понимаю, но я никак не могу въехать, насколько полно она моделирует процесс ДП. То, что памяти она (рекурсия) будет жрать немеряно, практически не вызывает сомнения. Надо бы поэкспериметировать на конкретных числах..


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


Michael_Rybak
*****

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

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


Цитата(lapp @ 14.11.2006 7:16) *

Классически, сдедовало бы рассмотреть цикл по параметру, двоичное представление которого занимает n бит:
0010101110
- в этом примере из 10 предметов выбраны 3-й, 5-й, 7-й, 8-й и 9-й.


Цитата(lapp @ 14.11.2006 7:16) *

Согласно принципу ДП, нужно сохранять результаты, полученные на предыдущих шагах. Например, если нужно выяснить вес комбинации
0010011101,
то можно воспользоваться тем, что мы уже знаем вес комбинации
0000011101,
и просто прибавить к ней вес 3-его предмета.



Для задачи о рюкзаке ДП можно применить не так.

Пусть функция f(m, w) равна максимальной общей ценности, которую можно получить, заполнив вес w, используя только первых m предметов. Тогда нас интересует f(n, 100). А f(i, j) легко выразить через предыдущие: f(i, j) = max(f(i - 1, j), price[i] + f(i - 1, j - weight[i]))

Теперь мы заполняем за один проход матрицу f, и получаем ответ. Сложность алгоритма - O(NW), где N - количество предметов, W - ограничение по общему весу.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


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

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

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


Цитата(Michael_Rybak @ 14.11.2006 12:29) *
Для задачи о рюкзаке ДП можно применить не так.
Пусть функция f(m, w) ...

Очень красиво.. smile.gif Респект!
Я не сразу врубился рекуррентное соотношение, пришлось несколько раз рассмотреть - но похоже, все верно.. Это ты сам придумал или взял где-то?

Но!.. Прав ли ты, называя это ДП - в этом я не вполне уверен. По сути, ДП не есть метод решения, то есть алгоритм. Это просто обычная скаредность: раз уж считаем много в переборе, то не выбрасывать же то, что нажито тяжким трудом - и больше ничего! smile.gif Твой же метод - это оригинальная разработка, основанная на конкретных свойствах моделируемой системы. Я не прав?

И еще: что ты думаешь о рекурсии? насколько она экономит вычисления? и экономит ли вообще?

PS
А может, именно это имел в виду автор темы, упоминая некие "таблицы"? smile.gif


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

Сообщений в этой теме


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

 





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