 |
|
|
 
|
|
Вечеринка в фирме, Т.Кормен 
| Shadowlord |
|
|||
|
Опытный  Профиль Группа: Участник Сообщений: 275 Регистрация: 28.11.2006 Репутация: нет Всего: 5 |
Пытаюсь разобраться задачкой из Т.Кормена с 311 16-4:
пока не могу придумать алгоритм, алгоритм должен быть рекурсивным но я что то не могу сообразить как он должен выглядит ps: пишу на C++ Это сообщение отредактировал(а) Shadowlord - 6.12.2009, 08:21 |
|||
|
||||
Загрузка ...
| PRF |
|
|||
 Шустрый Профиль Группа: Участник Сообщений: 135 Регистрация: 13.10.2007 Репутация: нет Всего: нет |
используй динамическое программирование., инфа есть в интернете! если его использовать, то задача решается очень быстро при больших входных данных..
правда сейчас сам алгоритм я не вспомню)) помню что надо начинать с нижних слоев дерева.. вот это точно, а дальше подниматься и вести таблицу посещаемости, ну это уже аспекты динамического программирования Это сообщение отредактировал(а) PRF - 26.11.2009, 17:16 |
|||
|
||||
| maxdiver |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
Да, видится простая динамика: для каждой вершины посчитать D1[v] - ответ для вершины i и всего её поддерева, если мы обязательно берём эту вершину, и D2[v] - то же самое, но если мы не берём вершину v. Тогда, чтобы посчитать D1[v] и D2[v], сначала посчитаем (рекурсивно) эти величины для всех её потомков, а потом D1[v] = СУММА D2[cv] по всем сыновьям cv вершины v, а D2[v] = СУММА max(D1[cv], D2[cv]).
|
|||
|
||||
| esperanto |
|
|||
 Бывалый Профиль Группа: Участник Сообщений: 194 Регистрация: 31.5.2003 Репутация: 2 Всего: 4 |
Это известаная задача нахождения наибольшего независимого подмножества вершин дерева.
Max independetn vertex set on tree --------------------
B.Sc ->M.Sc.->Microsoft SDE-> (Ph.D. student + Intel SDE + psyсhology B.A) - > Skype SDET |
|||
|
||||
| Shadowlord |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 275 Регистрация: 28.11.2006 Репутация: нет Всего: 5 |
maxdiver, так для каждой вершины V мы получаем два значение D1[v] и D2[v], и а как нам выбрать те вершины которые мы берем .
Да вот не совсем понятно как считать эти значения для листовых вершин. Это сообщение отредактировал(а) Shadowlord - 6.12.2009, 12:47 |
|||
|
||||
| maxdiver |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
По самому определению выходит, что для листьев D1[v] = Рейтинг[v], D2[v] = 0.
А для всех остальных вершин считаем по слоям: для листьев мы знаем, посчитаем значения для их непосредственных предков, потом для их предков, и т.д. Ну по слоям, как Вы сразу и написали. |
|||
|
||||
| Shadowlord |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 275 Регистрация: 28.11.2006 Репутация: нет Всего: 5 |
maxdiver, спасибо с дела, только формулы слегка изменил D1[v] =R[v]+ СУММА D2[cv] где R[v] вес(рейтинг) вершины
|
|||
|
||||
| maxdiver |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
Да, конечно, забыл само R[v] прибавить
 |
|||
|
||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.0828 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |