Минимальная масса леса данной мощности

11

Этот вопрос был мотивирован вопросом, заданным на stackoverflow .

Предположим, вам дано корневое дерево (т. Е. Есть корень, а у узлов есть дочерние элементы и т. Д.) На n узлах (обозначены 1 , 2 , , n ).Tn1,2,,n

Каждая вершина имеет неотрицательный целочисленный вес: w i .iwi

Кроме того, вам дается целое число , такое что 1 k n .k1kn

Вес из множества узлов S { 1 , 2 , ... , п } является суммой весов узлов: Е сек S ш с .W(S)S{1,2,,n}sSws

Даны входные данные , w i и k ,Twik

Задача состоит в том, чтобы найти подлес минимального веса * , T , такой, что S имеет ровно k узлов (т.е. | S | = > k ).STSk|S|=>k

Другими словами, для любого подлеска из T , такого что | S | = k , мы должны иметь W ( S ) W ( S ) .ST|S|=kW(S)W(S)

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

wi{0,1}

Кажется, это должно быть хорошо изученной проблемой.

Кто-нибудь знает, если это проблема NP-Hard / есть известный алгоритм времени P?


TSTxSxST

PS: Прошу прощения, если окажется, что я упустил что-то очевидное и вопрос действительно не по теме.

Арьябхата
источник
Я сильно подозреваю, что на это есть простой ответ, но это все еще разумный вопрос.
Суреш Венкат

Ответы:

7

ci{0,1}Sk=iSciCC

v(v)

Рико Джейкоб
источник
k
Хорошая точка зрения. Я изменю свой ответ соответственно.
Рико Джейкоб