algorithm - 0-1 有额外限制的背包（有色物品）？

Question

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

想象一下正常的 0-1 背包问题，除了所有物品都是黄色、红色、蓝色或绿色，并且由于您的强迫症，您的背包中每种颜色的物品必须恰好有 2 件。因此，每个项目都有 3 个属性，而不是普通项目：重量、值、颜色。

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

Answer 1

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