NP和近似算法的一道题
一个有向不循环图G =（V,E）有一个起点s和终点t。每条边e都有个长度L(e)>0和价值（payoff）P(e)>0。给定一个最大长度Lmax>0，要求找到一条能获得最大价值，且总长度不超过Lmax的s到t的通路（path）。
（a）证明这个问题是NP-HARD。（提示，利用特殊情况：每条边P(e)=L(e)）
（b）给出一个伪多项式时间的算法。就是说，给出一个算法，他的运行时间基于n（点的数量）,m（边的数量），和MAXe｛L(e)+P(e)｝（长度和价值的和最大的边）
（c）对任意x>0, 给出一个多项式时间的(1+x)-近似算法。算法必须绑定在n，m，1/x，log（Lmax）之上。
没有什么头绪。。希望大家帮帮忙。。。
[解决办法]
(a)再提示：把子集和问题reduce到这个问题上。
(b)拓扑排序以后DP
(c)让l=max(L(e))，然后修改图使得新的L'(e)=ceil(L(e)/K)，其中K=x*l/n。在新的图上用(b)的DP算法，它符合要求。证明先自己想想看。
