Just as classic knapsack problem, we want to maximize the total value while do not let the total weight exceed the capacity, and their values and weights are independent. But, for some items, if you want to select it, you have to select some other items.
For exmaple: There are item_1, item_2, ..., item_n. If you want to select item_1, you have to select item_3 and item_5, and if you want to select item_3, you have to select item_2, item_7, item_9... etc.
The dependencies are independent, that is, if we draw the dependency graph, it is just a "directed graph".
First, I noticed "precedence constrained knapsack problem" and "partially ordered knapsack problem", but in my problem, the dependency doesn't follow antisymmetric (that is, the dependency graph may contain cycles).
The closest problem I found is "set-union knapsack problem"
Given a set of items, select the subset with largest total value, subject to the constraint that the total weight of the items selected does not exceed a fixed capacity. The total value of a set of items is the sum of the individual values and the total weight is the sum of the individual weights. In the Set-Union Knapsack Problem, the items each have a value, but instead of a weight, each corresponds to a set of elements. Each element has a weight. The total value of a set of items is sum of the individual values, but the total weight is the sum of the weights of the elements in the union of the corresponding sets.
But it only unions the "weights", the value of some items may accumulate several times.
Is there any way to efficiently solve this problem?
EDITED:
I found a way which I can leverage some approximation algorithm
step 1. Make a directed dependency graph
step 2. Transfer this graph to component graph (use DFS to find strongly connected component) to remove cycle
step 3. So now, this become a "precedence constrained knapsack problem" or "partially ordered knapsack problem". These are strongly NP-complete but there were a lot of papers talk about this, and can find a approximation algorithm to solve.
