# Path of maximum value with bounded cost in DAG

Consider a Directed Acyclic Graph in which every node has a value and a cost and edges do not have any weight. I need to find a path containing nodes such that sum of values of these nodes is maximized, but sum of cost over all these nodes must be at most C.

I am thinking of some modification of Dijkstra's algorithm. Any ideas? Is there any standard algorithm for this?

Consider a SUBSET SUM instance with weights $$w_1,\ldots,w_n$$ and target $$C$$. We create an instance of your problem, with the same value of $$C$$. There are $$n+1$$ nodes $$v_1,\ldots,v_n$$, where node $$v_i$$ has cost and weight $$w_i$$. There is an edge from $$v_i$$ to $$v_j$$ iff $$i < j$$.

Any directed path in this DAG corresponds to a subset of the weights $$w_1,\ldots,w_n$$. You are thus looking for a subset of the weights with maximal sum under the constraint that the sum is at most $$C$$. Thus the solution to your problem is $$C$$ iff the SUBSET SUM instance is a Yes instance.