![]() |
|
Модераторы: Poseidon |
![]()
|
|
| Hatabich |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 2 Регистрация: 18.10.2008 Репутация: нет Всего: нет |
Добрый день уважаемые программисты. У меня курсовая и задали такую задачу.
Задача. "Двоичная яблоня". Яблоня называется двоичной, если в каждой точке ветвления ствол или ветвь разделяется надвое. Точки ветвления, корень и концы веток - это узлы дерева. Известна масса каждого участка яблони между двумя смежными узлами. Первоначально в яблоне N узлов, а нужно оставить M. Яблоню можно резать в основаниях ветвей, при этом ветвь и вся часть дерева, растущая выше от разреза, удаляются. Исходные данные: N, M (1<M<N<100) и список из N-1 тройки. Каждая тройка содержит номера узлов, определяющих участок, и его массу (узлы пронумерованы от 1 до N). Требуется найти план подрезки дерева, оставляющий наименьшую суммарную массу оставшихся участков. Например, для исходных данных: N=8, M=3 и набора троек (1,2,19) (2,4,13) (3,2,12) (3,8,17) (3,6,11) и (5,8,10) (8,7,8). Результат может быть следующим: Обрезать ветви: (2,4) (3,8) (3,6) Методы которыми можно выполнить: 1) Ветвей и границ 2) Динамического программирования Дело вот в чем, я не понимаю эту задачу вообще. А методы Ветвей и границ и Динамического программирования оба я знаю. Подскажите кто нить как ее сделать, хоть алгоритм. :conf used:Хоть нарисуйте это дерево что примерно из себя представляет, Я вообще не могу понять про тройку. Кто нить чем нить помогите. |
|||
|
||||
| MetalFan |
|
|||
![]() Аццкий Сотона ![]() ![]() ![]() ![]() Профиль Группа: Комодератор Сообщений: 3815 Регистрация: 2.10.2006 Где: Moscow Репутация: нет Всего: 128 |
Для домашних заданий, курсовых, существует "Центр Помощи".
Тема перенесена! -------------------- There are always someone smarter than you... |
|||
|
||||
![]()
|
| Правила форума "Центр помощи" | |
|
|
ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Более подробно с правилами данного раздела Вы можете ознакомится в этой теме. Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Центр помощи | Следующая тема » |
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |