Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Вечеринка в фирме

Автор: Shadowlord 23.11.2009, 17:28

Пытаюсь разобраться задачкой из Т.Кормена с 311 16-4:

Код


Профессору поручено устроить вечеринку в фирме "ООО КЛМН".
Структура фирмы иерархична:отношение отношение подчиненности 
задано деревом, корень которого директор. Отдел кадров знает рейтинг
 каждого сотрудника(действительное число).
Чтобы всем было весело, директор распорядился, чтобы никто не оказался
 на вечеринки вместе со своим непосредственным начальником.

а. Разработать алгоритм,   составляющий список приглашенных с  наибольшем суммарны рейтингом

пока не могу придумать алгоритм, алгоритм должен быть рекурсивным но я что то не могу сообразить как он должен выглядит

ps: пишу на C++

Автор: PRF 26.11.2009, 02:01

используй динамическое программирование., инфа есть в интернете! если его использовать, то задача решается очень быстро при больших входных данных..

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

Автор: maxdiver 3.12.2009, 01:41

Да, видится простая динамика: для каждой вершины посчитать D1[v] - ответ для вершины i и всего её поддерева, если мы обязательно берём эту вершину, и D2[v] - то же самое, но если мы не берём вершину v. Тогда, чтобы посчитать D1[v] и D2[v], сначала посчитаем (рекурсивно) эти величины для всех её потомков, а потом D1[v] = СУММА D2[cv] по всем сыновьям cv вершины v, а D2[v] = СУММА max(D1[cv], D2[cv]).

Автор: esperanto 5.12.2009, 13:09

Это известаная задача нахождения наибольшего независимого подмножества вершин дерева.
Max independetn vertex set on tree

Автор: Shadowlord 6.12.2009, 10:57

maxdiver, так для каждой вершины V мы получаем два значение D1[v] и D2[v], и а как нам выбрать те вершины которые мы берем .
Да вот не совсем понятно как считать эти значения для листовых вершин.

Автор: maxdiver 9.12.2009, 14:03

По самому определению выходит, что для листьев D1[v] = Рейтинг[v], D2[v] = 0.

А для всех остальных вершин считаем по слоям: для листьев мы знаем, посчитаем значения для их непосредственных предков, потом для их предков, и т.д. Ну по слоям, как Вы сразу и написали.

Автор: Shadowlord 10.12.2009, 22:51

maxdiver, спасибо с дела, только формулы слегка изменил D1[v] =R[v]+ СУММА D2[cv] где R[v] вес(рейтинг) вершины

Автор: maxdiver 11.12.2009, 01:44

Да, конечно, забыл само R[v] прибавить smile