我有一个图表
具有起始节点“S”。
从'S'开始到图中每个节点只有一条路径
每个节点都有一个权重
每条边都被加权，它是在它连接的节点之间移动的成本。而且这个成本是一次性的，即一旦我们从'S'移动到'N1'，'S'和'N1'之间的 future 移动就不会涉及成本
问题是 - 给定一个数字 B ，从“S”开始旅行，使得所访问节点的权重总和最大化，并且遇到的成本小于或等于 B。
对不起，我没有权利在这里发布图片。所以这是一个外部链接:
http://postimg.org/image/4fpf0xtkp/
例如在上图中我可以如下遍历:
S->N1->N2->N1->N3->N4 节点权重 = N1+N2+N3+N4(最大化) 和总成本L1+L2+L3+L4(在B内)
感谢您的帮助!
最佳答案
你的问题是 NP-hard。要看到这一点，假设您有节点 S，并且每个其他节点都通过一条边连接到 S，并且没有其他边。进一步假设每个节点的权重等于其边缘的成本。然后，对于给定的目标最大成本 B，如果你能解决你的问题，那么你就可以解决子集总和问题(给定 B，确定是否有一个成本子集加起来恰好等于 B)。因此，您的问题是 NP-hard 问题，可能没有快速算法来解决它。蛮力方法很简单，最终可能是最好的方法。
关于algorithm - 遍历加权边时最大化节点权重和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24917449/