1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.