Помощь - Поиск - Пользователи - Календарь
Полная версия: Динамическое программирование
Форум «Всё о Паскале» > Разработка ПО, алгоритмы, общие вопросы > Алгоритмы
Slav
Вечер добрый.
Поставлена такая задача которую надо решить с помощью таблиц и динамического программирования предположительно. Пираты попали на остров, у них есть лодка которая может перевезти 100 кг, они нашли сокровища (различные) каждое из которых имеет свой вес и ценность, надо переветси такие сокровища, чтобы они имели максимальную ценность и общий вес их был <=100 кг (вместимость лодки).
Заранне благодарю
volvo
Язык программирования какой?
Гость
Извини, забыл. На С, желательно для компилятора Visual Studio
Алена
Задача о рюкзаке в чистом виде smile.gif

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

Дальше справишься, или нужна помощь?
Lapp
Цитата(Алена @ 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 экономия довольно значительная, но и память нужна немалая.. Рекурсия же делает нечто подобное, как я понимаю, но я никак не могу въехать, насколько полно она моделирует процесс ДП. То, что памяти она (рекурсия) будет жрать немеряно, практически не вызывает сомнения. Надо бы поэкспериметировать на конкретных числах..
Алена
Цитата
как быть с упомянутым динамическим программированием (ДП)
У автора сказано
Цитата
задача которую надо решить с помощью таблиц и динамического программирования предположительно.
Значит, возможны и другие варианты? Или я ошибаюсь?
Lapp
Цитата(Алена @ 14.11.2006 11:24) *

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

Русский язык велик и могуч! smile.gif
Я думаю, что оригинальная формулировка могла быть, например, такая:
"Условие: ... Решение предполагается с использованием ДП."
И тут уж слово "предполагается" звучит императивно smile.gif.
Также следует учесть то, что ДП вынесено в заголовок. И наконец - довольно вольное обращение автора с "Великим и могучим" (пренебрежение пунктуацией, опечатки..) smile.gif
Алена, если ты внимательно читала, ты могла заметить, что мой вопрос состоит именно в сравнении методов, для чего я и изложил суть классического подхода ДП. Более того, мне кажется, что рекурсия в данном случае как бы работает аналогично ДП. Вот мне и хотелось бы выяснить, насколько именно аналогично, раз уж речь зашла (а она все-таки зашла) о ДП.
Я понятно излагаю? smile.gif
Michael_Rybak
Цитата(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 - ограничение по общему весу.
Lapp
Цитата(Michael_Rybak @ 14.11.2006 12:29) *
Для задачи о рюкзаке ДП можно применить не так.
Пусть функция f(m, w) ...

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

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

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

PS
А может, именно это имел в виду автор темы, упоминая некие "таблицы"? smile.gif
Michael_Rybak
Дело в том, что этот метод, который я здесь описал - это что-то вроде хрестоматийного примера по ДП 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
Lapp
Круто! smile.gif
У меня о ДП было несколько другое представление.. Надо почитать.. Anyway, спасибо за разъяснение smile.gif
PS
в такой трактовке теме следовало бы быть в новом разделе, который хочет открыть Altair - Теоретические вопросы программирования или что-то в этом роде.. А после некоторой доработки - в FAQ smile.gif
Michael_Rybak
Цитата(lapp @ 14.11.2006 13:24) *

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


Всегда рад smile.gif
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.