algorithm - 这可以在多项式(或伪多项式)时间内解决吗？

Question

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

假设您有一堆球。每个球至少有一种颜色，但也可以是多色的。每个球都有一个重量和一个与之相关的值。还有一堆盒子，每个盒子只有一种颜色。每个盒子都有它可以容纳的最大球数。目标是在保持一定的总重量 W 的情况下最大化框中值的总和，唯一的规则是:

为了将球放入盒子中，它至少必须具有盒子的颜色

(例如，您可以将蓝色和绿色的球放入蓝色框或绿色框，但不能放入红色框。)

我做了一些研究，这似乎类似于背包问题，也类似于可以通过匈牙利算法解决，但我似乎无法将其归结为任何一个问题。

我只是好奇是否有某种动态规划算法可以解决此类问题，使其可以在多项式时间内解决，或者它是否只是变相的旅行商问题。如果我知道最多有 X 种颜色会有帮助吗？任何帮助是极大的赞赏。如果有帮助的话，我还可以用变量名将问题形式化一些。谢谢!

这是一个简单的例子:

最大重量: 5

球:

1 个红球 - (值 = 5，权重 = 1)

1 个蓝色球 - (值 = 3，重量 = 1)

1 个绿色/红色/蓝色球 -(值 = 2，重量 = 4)

1 个绿色/蓝色球 - (值 = 4，重量 = 1)

1 个红色/蓝色球 - (值 = 1，重量 = 1)

盒子:

1 个红色(持有 1 个球)

1 个蓝色(可容纳 2 个球)

1 个果岭(持有 1 个球)

最优解:

红盒子里的红球

蓝盒子里的蓝球和红/蓝球

绿色盒子里的绿色/蓝色球

总值:13(5 + 3 + 1 + 4)

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

注意:即使绿色/红色/蓝色球比红色/蓝色球更有值(value)，它的重量也会让我们超出限制。

编辑:

一个澄清点:具有相同颜色组合的球不一定具有相同的重量和值。例如，您可以有一个值为 3、重量为 1 的红球和另一个值为 2、重量为 5 的红球。

编辑 2:

如果它有助于我们提出动态规划算法，我们可以假设整数权重和值。

Answer 1

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

如果具有相同颜色组合的球必须具有相同的重量和值，请考虑这样一种情况，即您有红/蓝、红/绿等球并且只有一个红色框。