给出了根图 . 这里，节点是“家”，包含一些有 Value 的项目 . 给出入口节点，即图的根 .
还给出了从一个节点移动到另一个节点的成本，即Egde权重 .
Question -
您必须收集最大的贵重物品，总成本不应超过给定的成本 .
Contraint - 1.没有循环 . 2.我们也可以使用相邻矩阵 . （顶点总数最多为1000） .
Example
Edges given with their weight and values present in destination node.
0 1 10 1
0 2 10 15
1 3 50 10
1 4 30 30
Given Cost = 70 .
Solution - 您将以最大方式收集节点1,2,4的项目 . [1+15+30 = 46]
My efforts
我认为，这个问题将由DP解决，通过在每个节点维护一些状态 . 但我无法做出一些算法 . 请帮忙 .
Edit 1
-
我认为这个问题可以通过使用原始图形通过将某个状态添加到每个节点来制作特殊图形来解决 .
-
第二种方法是动态编程 .
1 回答
我认为你不会为这个问题找到一个简单的解决方案 .
考虑仅由连接到N个叶子的根节点制作的图表 . 每个叶子的值为1，边缘的成本为c1，c2，... cN .
正如您所看到的，这个图形问题具有背包问题作为一种特殊情况 .