algorithm - 计算给定路径成本下的最大利润

Question

给出了有根图。在这里，节点是包含一些有值(value)元素的“家”。给定入口节点，即图的根。

还给出了从一个节点移动到另一个节点的成本，即 Egde 权重。

问题 -

您必须收集最大值(value)的元素，并且总成本不应超过给定的成本。

约束 - 1.没有循环。 2.我们也可以使用邻接矩阵。(顶点总数最多为1000个)。

示例

给定边及其权重和存在于目标节点中的值。

0 1 10 1
0 2 10 15
1 3 50 10
1 4 30 30

给定成本 = 70。

解决方案 - 您将以最大方式收集节点 1、2、4 的项目。 [1+15+30 = 46]

我的努力

我认为，这个问题将通过 DP 来解决，通过在每个节点维护一些状态。但是我不能做一些算法。请帮忙。

编辑 1

1. 我认为这个问题可以通过在每个节点中添加一些状态来使用原始图来制作特殊图来解决。
2. 第二种方法是动态规划。

Answer 1

我认为您不会找到解决此问题的简单方法。

考虑一个由连接到 N 个叶子的根节点构成的图。每片叶子的值为 1，边的成本为 c1, c2, ... cN。

如您所见，这个图问题有一个特殊情况的背包问题。