Имеем взвешенное двоичное дерево. Необходимо получить подграф наибольшего веса, содержащий Q + 1 вершину, среди которых обязательно должна быть корневая.
Задача решается динамическим программированием.
Заведём рекурсивную функцию f, принимающую два параметра: количество вершин cnt и текущая вершина-корень root.
Вызовем её для левого и правого потомков, если они есть и cnt > 0. Вызовы возвратят массивы весов wLeft и wRight (их описание ниже), которые сохраним.
Заведём массив w[] длиной cnt + 1, и пусть w[i] — максимальный вес подграфа, содержащего i вершин.
У нас имеются массивы максимально возможных весов для подграфов, содержащих левого (wLeft) и правого (wRight) потомков. Заполним массив w.
Зададимся вопросом: а как получить подграф максимального веса? Нужно найти такие nLeft ≥ 0 и nRight ≥ 0, что nLeft + nRight = i и wLeft[nLeft] + wRight[nRight] = max.
Тогда вызвав res = f(Q, root), получим ответ в res[Q].
Комментариев нет:
Отправить комментарий