从列表中选择带限制的加权项目

Question

我有一个权重列表，其中每个索引表示一个物品的权重。

Weights = [0.3, 0.7, 0.1, 0.3, 0.1, ...]

每个项目都有一系列碰撞项目，因此如果您选择项目0，则无法选择项目1。

Item_0 = [0,1,3,7]
Item_1 = [1,5,6,8]

所有物品发生的碰撞次数相同。

目标是选择N个物品，考虑到碰撞并最大化所选物品的重量。

如何以最简单和最符合Python风格的方式实现？

我最初认为贪心算法可以解决问题（按重量降序排序），但它不起作用，我能想到的唯一其他解决方案是找到所有可能的N个物品组合（没有碰撞）并计算总重量。

贪心算法（给出错误结果）：

def pickTop_K(weights, collision_dict):
    ret = []

    while len(ret) < k:

        index = np.argmax(probs)
        ret.append(index)

        collisions = collision_dict[index]
        weights[collisions] = 0

        if np.max(weights) == 0:
            break

    return ret

- S. Salman

---

是的，所有元素都有相同数量的碰撞。我也编辑了问题。 - S. Salman

我认为这个问题与最大加权独立集有关：https://wincent.com/wiki/Computing_the_Maximum_Weighted_Independent_Set_of_a_graph_path - Dani Mesejo

那么对于第0项，你不能选择第0、1、3和7项？我只是在澄清。此外，这些项目只是Weights的索引吗？所以第0项-> 0.3，第1项-> 0.7等。 - RoadRunner

好的问题描述...在哪里可以找到试图解决它的代码，以及它的具体问题是什么？你能否发布一个详尽的物品/重量集合（或将你拥有的限制为一个简短的列表）？ - Patrick Artner

所以对于第0个项目，在我们选择了0之后，我们不能选择0、1、3和7。是的。 是的，这些项目只是权重的索引。问题在于，根据我的看法，得出最优解的解决方案将过于计算上不可行。我会添加我想出的贪心解决方案的代码，但我意识到它并不是最优的。 - S. Salman

Answer 1

我相当确定这个问题是NP难的。

然而，有一种方法可以解决它，同时限制你所做的工作量，具体如下。

首先，按权重降序排序顶点。

然后进行A*搜索。也就是说，你有一个优先队列，总是返回最高优先级的选项。一组选择的优先级是选择的总权重加上选择接下来几个顶点的权重上界。

在伪代码中，看起来像这样。

create priority queue paths
add to paths an empty set with weight the sum of the first n items.
while paths is not empty:
    take the top path from the queue.
    If the path is a set of n choices:
        that is your answer, return it
    else:
        Look for the next element that could or couldn't be added.
        If you found it:
            Add an option to the queue where you choose it
            Add an option to the queue where you don't choose it
        Else:
            This is a dead end.  Pass.

我最好的猜测是，最好估计上限的值。也就是说，找到实际上没有与任何现有选择冲突的顶点，并将它们相加以得到一个良好的上限。这个操作很昂贵，但可以减少分支。而选项的指数增长来自于分支——早期修剪分支是值得投资的。

如果贪心策略可行，这个算法会非常快地找到结果。如果某种接近贪心策略的方法可行，那么回溯不会太多。但如果你不幸的话，这会占据指数级的空间和内存。（但如果它确实是NP难问题，你不能指望做得比这更好。）

- btilly