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?

New contributor
iro otaku is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\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

iro otaku is a new contributor. Be nice, and check out our Code of Conduct.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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