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

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


Гость






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


Гость






Язык программирования какой?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






Извини, забыл. На С, желательно для компилятора Visual Studio
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






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

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

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


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

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


Гость






Цитата
как быть с упомянутым динамическим программированием (ДП)
У автора сказано
Цитата
задача которую надо решить с помощью таблиц и динамического программирования предположительно.
Значит, возможны и другие варианты? Или я ошибаюсь?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


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

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

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


Цитата(Алена @ 14.11.2006 11:24) *

У автора сказано <предположительно - lapp> Значит, возможны и другие варианты? Или я ошибаюсь?

Русский язык велик и могуч! smile.gif
Я думаю, что оригинальная формулировка могла быть, например, такая:
"Условие: ... Решение предполагается с использованием ДП."
И тут уж слово "предполагается" звучит императивно smile.gif.
Также следует учесть то, что ДП вынесено в заголовок. И наконец - довольно вольное обращение автора с "Великим и могучим" (пренебрежение пунктуацией, опечатки..) smile.gif
Алена, если ты внимательно читала, ты могла заметить, что мой вопрос состоит именно в сравнении методов, для чего я и изложил суть классического подхода ДП. Более того, мне кажется, что рекурсия в данном случае как бы работает аналогично ДП. Вот мне и хотелось бы выяснить, насколько именно аналогично, раз уж речь зашла (а она все-таки зашла) о ДП.
Я понятно излагаю? smile.gif


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


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


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

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

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


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

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

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

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

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


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


Michael_Rybak
*****

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

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


Дело в том, что этот метод, который я здесь описал - это что-то вроде хрестоматийного примера по ДП smile.gif

Главный принцип ДП заключается в том, что если задачу можно разбить на независимые подзадачи, то из оптимальности решения всей задачи обязана следовать оптимальность решения каждой из подзадач. Это может иметь некоторое отношение к перебору, а может и не иметь. Вопрос только в способе разбиения на подзадачи.

В данном случае f(m, w) описывает пространство подзадач: чтобы узнать, как оптимально заполнить вес w с помощью m предметов, мы должны либо взять m-ый, либо не взять, и в любом случае остальные предметы выбрать оптимально. Таким образом, подзадачей является решение данной задачи, с использованием *упорядоченной части* предметов и части предоставляемого веса.

Цитата(lapp @ 14.11.2006 11:37) *

Это ты сам придумал или взял где-то?


Именно это - может и сам, хотя я уже и не вспомню; мое первое знакомство с ДП состоялось на задаче про банкиров. У нас есть m денег, и n банкиров. Дана таблица A[i,j] - сколько заплатит банкир i, получив j денег. Надо распределить деньги между банкирами. Решается аналогично: f(x, y) - максимальная прибыль, которую можно получить, распределяя x денег между первыми y банкирами.

Насколько я помню, это было в 9м классе, т.е. 8 лет назад, и мне тогда довольно непросто было "въехать в тему" Беллмана, не то что самому ее придумать. С опытом, конечно, лучше стало smile.gif - и с ДП, и с придумываением (вместо въезжания) всякого разного.

Вообще на динамику очень много бывает красивых и сложных задач.


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


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

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

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


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

Код
for m
  for w
    f:=...

С другой стороны, DFS писать без рекурсии - мазохизм какой-то. Обычно по ограничениям задачи понятно, пройдет ли по времени рекурсия.

Если же говорить не об олимпиадных задачах, а о сложных проектах, то там, при необходимости, рекурсией грех пренебрегать, когда внутри рекурсивной процедуры выполяются достаточно трудоемкие операции - выигрыш в производительности при переходе к итеративному алгоритму будет несущественным, а readability и maintainability упадет dramatically.

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


Сдается мне, ОП как раз проходит основы ДП smile.gif

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


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

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

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


Круто! smile.gif
У меня о ДП было несколько другое представление.. Надо почитать.. Anyway, спасибо за разъяснение smile.gif
PS
в такой трактовке теме следовало бы быть в новом разделе, который хочет открыть Altair - Теоретические вопросы программирования или что-то в этом роде.. А после некоторой доработки - в FAQ smile.gif


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


Michael_Rybak
*****

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

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


Цитата(lapp @ 14.11.2006 13:24) *

Anyway, спасибо за разъяснение smile.gif


Всегда рад smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 





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