Ограничения алгоритма динамического программирования

Question

После изучения этого вопроса я понял, что алгоритмы динамического программирования не могут быть использованы для решения задачи о ранце или подобных проблем с нецелым ограничением .Я прав насчет своей реализации?Существуют ли другие ограничения алгоритмов динамического программирования?

Answer 1

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

Если существует только N возможных баллов решения, вы знаете, что в большинстве случаев вам нужно будет найти N из них, чтобы получить лучший, а не целое экспоненциальное количество способов добраться до них. Это идея динамического программирования.

Answer 2

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

Вот пример проблемы от Дэвида Эппштейна :

Учитывая отсортированный список из n действительных чисел, найдите наименьший интервал содержит ровно k элементов для всех значений k от 1 до n. Существует простой алгоритм динамического программирования, который решает эту проблему. проблема в квадратичном времени, но самая известная нижняя граница линейно. Либо опишите более быстрый алгоритм, либо докажите больший связаны в какой-то разумной модели вычислений. («Динамическое программирование» не разумная модель вычислений !!)