Consider a set of items, weighted with real numbers / costs. You are supposed to select a subset maximizing the sum of the weights of the selected items. But the following contraints must be observed: Every item can be selected only once. Some items have depedencies: If you select item 1, you also have to select item 2 and item 3. Note: Therefore, it's possible to have items with the following property: You must select item 1, if you select item 2 or item 3 (imagine a dependency graph) and there is no limit: You can select as many items as you want. Last, fragments of items (like 0.7 times item 1) are not allowed.I ask for an algorithm or some ideas to this problem.
Bounded 0/1-knapsack with dependency constraints without limit
graph algorithms