Домашнее задание 2.
Срок сдачи: 28/02/2000.

1.
Бинарное дерево можно описать индуктивно следующим способом:
(0)
Граф, состоящий из единственной вершины, является бинарным деревом.
(1)
Дерево может состоять из корня и не более чем двух поддеревьев, левого и правого. Причем дерево, содержащее только левое поддерево, не считается равным дереву, содержащему только правое поддерево, даже если эти поддеревья равны.

\epsfig{file=tree.eps}

Каково число деревьев с n вершинами?

2.
Можно ли в алгоритме \ensuremath{\textsc{Matrix-Chain-Multiply}}обоитись без матрицы s? Как изменится алгоритм?

3.
(Задача о рюкзаке). Вор забрался в магазин. У вора есть рюкзак, вместимостью не более чем W килограмм, и у него есть выбор из n предметов, вес каждого из которых равен wi, а стоимость -- vi ( $1\leqslant i \leqslant n$). Вор не может унести предметы с весом, большим чем вместимость рюкзака, и не может взять часть предмета. Какие предметы должен забрать вор, чтобы максимизировать стоимость предметов в рюкзаке V?

Напишите алгоритм динамического программирования для решения задачи о рюкзаке. Оцените его временную сложность. Является ли Ваш алгоритм алгоритмом полиномиальной сложности?

Указания: пространство подзадач состоит из всех задач вида V(k, w) нахождения оптимальной загрузки рюкзака предметами из множества первых k, с общим максимальным весом не более чем w.

4.
В стране Лимонии ходят в обращении монеты достоинством 1, 5 и 6 тугриков. Напишите алгоритм, который выдает любую сумму денег минимальным количеством монет.

5.
http://cmc.cs.msu.su/contest/problems/1998-1/c/


Alexander Chernov
2000-02-21