Задача. "Двоичная яблоня".
Яблоня называется двоичной, если в каждой точке ветвления ствол или ветвь разделяется надвое. Точки ветвления, корень и концы веток - это узлы дерева.
Известна масса каждого участка яблони между двумя смежными узлами. Первоначально в яблоне 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:Хоть нарисуйте это дерево что примерно из себя представляет, Я вообще не могу понять про тройку. Кто нить чем нить помогите.
