Этот вопрос был мотивирован вопросом, заданным на stackoverflow .
Предположим, вам дано корневое дерево (т. Е. Есть корень, а у узлов есть дочерние элементы и т. Д.) На n узлах (обозначены 1 , 2 , … , n ).
Каждая вершина имеет неотрицательный целочисленный вес: w i .
Кроме того, вам дается целое число , такое что 1 ≤ k ≤ n .
Вес из множества узлов S ⊆ { 1 , 2 , ... , п } является суммой весов узлов: Е сек ∈ S ш с .
Даны входные данные , w i и k ,
Задача состоит в том, чтобы найти подлес минимального веса * , T , такой, что S имеет ровно k узлов (т.е. | S | = > k ).
Другими словами, для любого подлеска из T , такого что | S ′ | = k , мы должны иметь W ( S ) ≤ W ( S ′ ) .
Если число дочерних элементов каждого узла было ограничено (например, двоичные деревья), то существует алгоритм полиномиального времени, использующий динамическое программирование.
Кажется, это должно быть хорошо изученной проблемой.
Кто-нибудь знает, если это проблема NP-Hard / есть известный алгоритм времени P?
PS: Прошу прощения, если окажется, что я упустил что-то очевидное и вопрос действительно не по теме.
Ответы:
источник