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