寻找具有目标成本的生成树
我对这个很困惑。刚开始发帖，如果这是一个愚蠢的问题，请原谅我。
假设我们有一个带有加权边的图 G=(V,E)。我想创建 G 的生成树，目标成本为 c，其中生成树的成本定义为其所有边成本的总和。我们如何判断是否存在成本为c的G生成树？
I'm quite stumped on this one. New to posting, so forgive me if this is a silly question.
Say we are given a graph G=(V,E) with weighted edges. I would like to create spanning tree of G with a target cost of c, where a spanning tree's cost is defined as the sum of all its edge costs. How do we determine if there exists a spanning tree of G with cost c?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这是一个尝试。您可以使用动态规划来解决子集和问题，然后对于每个可能的子集，只需检查它是否形成生成树。子集和的一般公式为：令 C[i,S] 为语句的布尔值
令 e 为任意边。然后递归通常是这样的：
（您要么使用边 e，要么不使用，并确保使用边e 不形成循环）。
如果目标成本为 c，则需要对每个 1 <= i <= c 执行 n 次扫描，其中 n 是边数。
最后验证选取的边数是否比顶点数少 1，并且它们都是相连的。
另一种方法是仅使用回溯递归来搜索所有生成树<= targetCost。
Here's a stab at it. You can use dynamic programming to solve the subset sum problem then for each possible subset just check if it forms a spanning tree. The general formulation of subset sum goes: let C[i,S] be the boolean value of the statement
Let e be an arbitrary edge. Then the recurrence usually goes:
(you either use edge e or you don't and make sure that using the edge e doesn't forms a cycle).
If the target cost is c then you need to perform n sweeps for each 1 <= i <= c where n is the number of edges.
Finally verify that the number of edges picked is 1 less than the number of vertices and they are all connected.
The other approach is to just use backtracking recursion to search all spanning trees <= targetCost.