具有相关选择的背包问题

Question

就像经典的背包问题一样，我们希望在不让总重量超过容量的情况下，使总价值最大化，并且它们的值和权重是独立的。但是，对于一些项目，如果您想要选择它，您必须选择一些其他项目。

例如:有item_1，item_2，…，item_n。如果你想选择item_1，你必须选择item_3和item_5，如果你想选择item_3，你必须选择item_2，item_7，item_9.等。

依赖关系是独立的，也就是说，如果我们绘制依赖关系图，它就是一个“有向图”。

首先，我注意到了“优先约束背包问题”和“偏序背包问题”，但在我的问题中，依赖关系并不遵循反对称(也就是说，依赖关系图可能包含循环)。

我发现的最接近的问题是“集并背包问题”。

给定一组项目，选择具有最大总价值的子集，但所选项目的总权重不超过固定容量的约束条件。一组项目的总价值是单个值的总和，总权重是单个权重的总和。在Set-Union背包问题中，每个项目都有一个值，但每个条目都对应于一组元素，而不是一个权重。每个元素都有一个权重。一组项目的总价值是单个值的总和，而总权重是相应集合中元素的权重之和。

但它只结合了“权数”，某些项目的价值可能会累积好几次。

有没有办法有效地解决这个问题？

编辑：

我找到了一种可以利用一些近似算法的方法

步骤1.制作有向依赖图

步骤2.将此图转换为组件图(使用DFS查找强连接组件)以删除循环。

因此，现在，这变成了“优先约束背包问题”或“部分排序背包问题”。这些都是强NP-完全的，但是有很多论文都讨论过这一点，并且可以找到一个近似算法来解决。

Answer 1

在选择项目之前，您必须检查天气项目是否会创建循环，如果它创建了循环，然后放弃它并移到下一个项目。为此，您可以使用Kruskal的算法。