Hi everyone,

Previously I learned about the Dependent Knapsack Problem on Trees, which the dependency graph of items form a tree. For a general dependency graph, we can bunch all items in the same SCC into a single item, which results in a DAG. Is there an efficient solution to this Dependent Knapsack Problem on DAGs? If it does, is it possible to come up with an $$$O(NW)$$$ solution? I searched the problem and didn't find much useful information.

Problem statement: We have a knapsack that can hold a maximum weight $$$W$$$. There are $$$N$$$ items to choose from, each item $$$i$$$ has its own weight $$$w_i$$$, value $$$v_i$$$ and a set of dependencies $$$S_i$$$. To choose item $$$i$$$, we must choose (all elements/at least one element) in $$$S_i$$$ if $$$S_i$$$ is non-empty. What is the maximum total value we can get in our knapsack?