algorithm - 0-1 有额外限制的背包(有色元素)？

Question

我正在研究这个问题，主要是出于对工作停工时间的好奇。

想象一下正常的 0-1 背包问题，除了所有元素都是黄色、红色、蓝色或绿色，并且由于您的强制症，您的背包中每种颜色必须恰好有 2 件元素。因此，与普通元素不同，每个元素都有 3 个属性:重量、值(value)、颜色。

这仍然是一个背包问题，还是用其他方式更好地定义？

Answer 1

为了便于输入，我将使用 nCk 来表示“n 选择 k”。由于每种颜色必须恰好有 2 个项目，因此可行解的数量为 O(nC2)，即 O(n^2)。每个解决方案都可以在多项式时间内进行评估，因此该问题也可以在多项式时间内解决。换句话说，它比常规的背包问题要简单得多。