Динамическое программирование Опции

[Slav]

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

[volvo]

Язык программирования какой?

[Гость]

Извини, забыл. На С, желательно для компилятора Visual Studio

[Алена]

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

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

Дальше справишься, или нужна помощь?

[Lapp]

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

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

[Алена]

как быть с упомянутым динамическим программированием (ДП)

У автора сказано

задача которую надо решить с помощью таблиц и динамического программирования предположительно.

Значит, возможны и другие варианты? Или я ошибаюсь?

[Lapp]

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

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

[Michael_Rybak]

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

Согласно принципу ДП, нужно сохранять результаты, полученные на предыдущих шагах. Например, если нужно выяснить вес комбинации
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]

Для задачи о рюкзаке ДП можно применить не так.
Пусть функция f(m, w) ...

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

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

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

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

[Michael_Rybak]

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

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

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

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

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

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

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

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

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

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

Код

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

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

Код

for m
  for w
    f:=...

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

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

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

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

Сообщение отредактировано: Michael_Rybak - 14.11.2006 17:04

[Lapp]

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

[Michael_Rybak]

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

Всегда рад