Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://sp.cs.msu.ru/courses/alg/task2/index.html
Дата изменения: Fri Oct 31 19:59:00 2008 Дата индексирования: Mon Oct 1 22:09:50 2012 Кодировка: koi8-r |
Каково число деревьев с n вершинами?
Напишите алгоритм динамического программирования для решения задачи о рюкзаке. Оцените его временную сложность. Является ли Ваш алгоритм алгоритмом полиномиальной сложности?
Указания: пространство подзадач состоит из всех задач вида V(k, w) нахождения оптимальной загрузки рюкзака предметами из множества первых k, с общим максимальным весом не более чем w.