小编Mik*_*nry的帖子

我正在研究涉及逻辑电路的研究问题(可以表示为DAG).DAG中的每个节点都有一个给定的权重,可以是负数.我的目标是找到一个连接的子图,使得节点权重之和最大.

给定边缘权重的最大权重连接子图问题显然是NP难的,但我希望的是有向非循环性质以及我处理节点权重而不是边权重的事实使得问题更容易一些.有人能指出我如何开始攻击这个问题的正确方向吗？

谢谢