这在多项式（或伪多项式）时间内是可解的吗？

Question

我正试图为这个问题想出一个合理的算法：

（例如，你可以把一个蓝色和绿色的球放进蓝色盒子或绿色盒子里，但不能放进红色盒子里。）

我做了一些研究，这似乎类似于背包问题，也类似于匈牙利算法可以解决的问题，但我似乎不能把它简化为任何一个问题。

我只是好奇，对于这种类型的问题，是否有某种动态规划算法，可以在多项式时间内求解，或者它只是变相的旅行商问题。如果我知道最多有X种颜色会有帮助吗？非常感谢任何帮助。如果有帮助的话，我也可以用变量名来形式化这个问题。谢了！

下面是一个简单的例子：

最大重量：5

球：

1红（持有1球）

1蓝（持有2球）

1个果岭（持有1球）

总重量:4(1+1+1+1)

注意：尽管绿/红/蓝球比红/蓝球更有价值，但它的重量会让我们超过极限。

编辑：

Answer 1

这至少和背包问题一样复杂--考虑一个所有球都是红色的，只有一个红色盒子的情况。

在具有相同颜色组合的球必须具有相同的重量和值的情况下，考虑一个情况，当你有红/蓝、红/绿等球和只有一个红框。