这是一个自我制定的问题的一部分，因此我无法“谷歌”它，我自己的尝试到目前为止都是徒劳的。
给你一个图G(V,E) V的每个节点都有利润wi， E的每个边都有成本ci。我们现在给定一个预算C，需要找到一条路径，使得成本总和小于C，其中wi的总和最大。路径在这里具有正常定义，即路径不包含重复顶点（简单路径）。
很明显，哈密顿路径是这种情况的一个特例（设置成本 = |N-1| 并且每个边的成本 = 1），因此这是一个 NP Hard 问题，所以我正在寻找近似解决方案和启发式方法.
数学上
给定图G(V,E)
对于每条边e ， ci >=0
对于每个顶点v ， wi >=0
找到一条简单的路径P使得
在P <= C中的所有边e上求和ci
最大化P中所有v的总和 wi
这被称为选择性旅行推销员问题，或有利润的旅行推销员。谷歌学术应该可以给你一些参考。经常使用诸如遗传编程或禁忌搜索之类的元启发式方法。如果您想以最佳方式解决问题，线性编程技术可能会起作用（不幸的是，您没有说明您正在处理的实例的大小）。如果路径的长度很短（比如 15 个顶点），颜色编码也可能有效。
定义权重增加并随着成本减少的价值函数。例如：
value(u,v) = w(v) / [c(u,v) + epsilon]
(+ epsilon for the case of c(u,v) = 0)
现在，这个想法是：
从一个 vertex ，以概率u继续到 vertex ：v
P(v|u) = value(u,v) / sum(u,x) [ for all feasible moves (u,x) ]
重复直到无法继续。
此解决方案将为您提供一个解决方案 - 快速，但它可能不是最佳的。然而——它是随机的——你总是可以在你有时间的时候一次又一次地重新运行它。
这将为您提供解决此问题的任何时间算法，这意味着-您拥有的时间越多-您的解决方案就越好。
一些优化：
max{value(u,v)}