算法具有2个限制的背包

Question

如果一直在进行一个项目，我遇到以下情形： 需要从一组M中选择N = 2个框，而M> N的权重总和最好，但有2个限制：

• 我们无法选择相同的框颜色
• 我们无法选择相同的方块ID

箱子自带的顶部

最高的权重排序0

我选择（RED1，请分享帮助）与朴素算法开始权重最高RED1，我们无法添加蓝天，因为我们有相同的ID 1，并且不可能添加RED2以及因为我们有红色盒子在10的权重下，我们以11的总权重结束，但如果我们选择Blue1，我们可以以18.9结束Red2 N可以大于2.

这是一个NP难题吗？ 更好的运行时间效率的解决方案吗？

Answer 1

我们可以用复杂O(2^color * 2^id * M * N)或回溯+修剪使用DP解决方案的复杂O(M choose N)

所以它取决于有多大的约束为M，N，颜色和编号。