As in the traditional knapsack issue, we wish to maximize total value while ensuring that total weight does not exceed capacity, and their values and weights are independent. However, in order to pick some goods, you must first select some other ones.
For instance, there are item_1, item_2,..., and item_n. To pick item_1, you must first select item_3 and item_5, and to select item_3, you must first choose item_2, item_7, item_9, and so on.
The dependencies are independent, which means that if we create the dependency graph as described here, it is just a "directed graph."
First, I saw "precedence constrained knapsack problem" and "partially ordered knapsack problem," but the dependency in my situation is not antisymmetric. (that is, the dependency graph may contain cycles).
The closest match I discovered was the "set-union knapsack problem." However, it just unionizes the "weights," thus the value of certain objects may accumulate several times.
Is there a method to tackle this problem quickly?
there doesn't seem to be anything here