Comments 17
Cпособ решения сложных задач путём разбиения их на более простые подзадачи называется декомпозицией.
А можно пример решения этой же задачи методом "нединамического программирования"? Или все что не рекурсия это динамическое программирование? Хочу понять в чем тогда смысл этого термина.
Даже если рекурсия, то все равно динамическое =) в некоторых языках только рекурсия и есть, например!
Какой именно из задач? Если чисел фибоначчи, то можно, например, реализовать рекуррентную формулу тупо по определению, но не делать мемоизации. Или можно перебирать все битовые строки заданной длины, не ставя две единицы подряд. Будет одинаковая экспоненциальная сложность по времени.
Динамическое программирование - это рекурсия + запоминание. Но не к любой рекурсии вы запоминание можете прикрутить - а только там, где у вас чистые функции: никакого глобального состояния и сайд-эффектов. Ну, и у этих параметров не должно быть слишком много вариантов значений. Иначе прикрутить-то прикрутите, но никакого ускорения вы не получите.
Шляпа какая-то. Термин встречается в математических книгах, но почему "программирование" и почему "динамическое", ерунда какая-то. Обычный расчетный алгоритм, каковых миллионы. Но другим алгоритмам не пытаются дать звучных математических имён.
Хотя что-то я замечтался, проще обратиться к Википедии, там всё разложено по полочкам:
Слово «программирование» в словосочетании «динамическое программирование» в действительности к «традиционному» программированию (написанию кода) почти никакого отношения не имеет и имеет смысл как в словосочетании «математическое программирование», которое является синонимом слова «оптимизация». Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи. К примеру, определённое расписание событий на выставке иногда называют программой. Программа в данном случае понимается как допустимая последовательность событий.
Словосочетание «динамическое программирование» впервые было использовано в 1940-х годах Ричардом Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей.
но почему "программирование"
Ну вот такой термин из математики. К программированию, как таковому, тут он отношения не имеет. Есть еще, например, задачи линейного программирования. Там вообще математическая теория и ручная работа с матрицами - алгоритмами и программированием особо и не пахнет (хотя решение этих задач, конечно, можно и в компьютере реализовать).
"Рекурсия – это термин в программировании, означающий вызов функцией самой себя. Рекурсивные функции могут быть использованы для элегантного решения определённых задач. Когда функция вызывает саму себя, это называется шагом рекурсии. База рекурсии – это такие аргументы функции, которые делают задачу настолько простой, что решение не требует дальнейших вложенных вызовов."
Привяжусь к картинке про динамическое программирование vs. рекурсия. Нет, рекурсивный алгоритм с запоминанием - это то же самое динамическое программирование, только реализованное сверху вниз. Реализация циклом по таблице - это реализация снизу вверх (об этом вы дальше даже пишите). Это просто 2 подхода. Практически любой алгоритм ДП можно реализовать и так и эдак.
Подход сверху вниз хорош тем, что он не счичтает лишние состояния - только те, которые реально влияют на ответ. Но ему нужен стек. Подход снизу вверх часто получается короче в реализации и позволяет, например, сократить используемую память, за счет хранения только двух строк/срезов всей таблицы (как в фиббоначи надо только 2 переменные).
Еще проблема в статье - что ДП не разбивает задачу на более маленькие подзадачи, а сводит заданную задачу к таким же, но "поменьше". Как выше уже заметили - упомянутое вами разбиение - это декомпозиция, а не динамическое программирование.
В этой задаче у нас есть набор предметов с определенной стоимостью и весом, а также рюкзак с ограниченной вместимостью. Нужно выбрать такой набор предметов, чтобы их суммарная стоимость была максимальной, а их суммарный вес не превышал вместимость рюкзака.
Прошу прощения за занудство, но из-за подобных формулировок решение может застопориться уже на этапе чтения задания.
Если под вместимостью в данном случае понимается грузоподъёмность, то почему бы так и не написать?
Конечно, можно и к словам придераться, но в условии все однозначно расписано:
а их суммарный вес не превышал вместимость рюкзака
Имеется:
рюкзак, обладающий вместимостью 0,2 м3 и грузоподъёмностью 10 кг.
плюшевый гремлин объёмом 1 м3 и массой 3 кг
металлическая болванка объёмом 0,03 м3 и массой 32 кг.
Гремлин проходит по массе, а по габаритам - нет.
Болванка проходит по габаритам, а по массе - нет.
Догадаться, разумеется, можно, особенно при наличии примеров. Но лично я считаю, что нужно стараться избегать неоднозначности трактовок. Чёткое формулирование - это тоже искусство. Реальность существует
В задаче объем объектов вообще не упоминается. Да, не корректно вместимость мерять в киллограмах, тут вы правы. Но на понимание задачи это никак не влияет. Можно это свойство рюкзака хоть "пепячностью" обозвать и мерять в джеки-чанах, если у условии указать, что суммарная упячность предметов не превосходит пепячность рюкзака.
2.2218473450011516
Отвратительно получилось. Алгоритм очень медленный. Так давайте улучшим его!
...
0.00414187600108562
Невероятно! Скорость выполнения повысилась в 2 раза!
...
[вывод на печать не показан]
Зависимость от n практически линейна!
Что тут вообще происходит?!
2/0.004 = 500 раз вообще-то, а не 2 раза
Как можно делать выводы о линейной зависимости от
n, посчитав результат только один раз (и не показав его в статье) для конкретногоn? Вы умеете рисовать линию по одной (невидимой) точке?
Очень наглядно и понятно разобрана задача для ряда Фибоначчи. Но следом за ней - сразу решение для задачи рюкзака, без каких-либо объяснений. При том, что она уже двухмерная, то есть это другой уровень сложности. Это домашнее задание типа "изучи сам"? А статья тогда зачем?
Слишком резкий скачок от максимально понятного изложения к непонятному.
О динамическом программировании на пальцах