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

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

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

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

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

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

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

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

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

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

Пусть функция 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 - ограничение по общему весу.

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

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

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

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

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

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

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



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

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

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




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

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



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


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

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



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

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

Всегда рад