是这个问题NP-很难吗？

Question

我试图拿出一个合理的算法对此问题：

让我们说你有一大堆球。每个球至少有一个颜色，但还可以多彩。每个球也有一个号码就可以了。还有一堆盒子，它是每一个只有一种颜色。我们的目标是最大限度的数字的总和在球在箱子，唯一的规则是：

• 为了地球在一个盒子， 已经为至少有箱子的颜色 上它
• 你只能投一球的每 盒。

例如，你可以把一个蓝色和绿色的球到蓝箱或绿箱，但是不到一个红盒子。

我已经有一些优化，帮助很多方面的运行时间。例如，可以排序球从大到小的顺序依次点值。然后，你去从最高数量以最低的，如果球只有一种颜色的，并且没有其他更高-点球包含的那个颜色,你可以把它放在那个盒子(并因此删除那个箱子和那个球从剩余的组合)。

我只是好奇的是有种动态的算法对于这种类型的问题，或者如果它只是个旅行推销员问题的化身。我知道有在最X颜色？任何帮助是极大的赞赏。谢谢！

---

编辑-这里有一个简单的例子：

球：

• 1红色球-5点
• 1蓝色球-3点
• 1绿色和红色球-2点
• 1绿色和蓝色球-4点
• 1红蓝色的球-1点

盒子：

• 1红色
• 1蓝色的
• 1绿色

最佳的解决方案：

• 红色的球在红盒子
• 蓝球的蓝色的盒子

• 绿色蓝球绿箱

  总值：12点(5 + 3 + 4)

Answer 1

这是一个特殊的情况下 最大重量匹配的问题上加权分图.建造一个图，其左顶点对应到球，他们的权利顶点对应的箱子和边缘参加球和框中具有重V在哪里V号球上如果球可以放在箱，否则为0。增加额外的箱子或者球加入另一侧与边缘的权重为零，直到你有同样数量的顶点。指派你要找的是确定设置的边缘零量最大(总数)重匹配所得的图表。

分配算法可以解决O(n^3)时间，其中n为这里的最大的球的数量或箱，使用 匈牙利算法.(顺便说一句，我应该做的声明，我仅提及匈牙利算法，因为它是理论上的结果，我碰巧很熟悉，它推测回答的问题是在标题是否是原始的问题是NP-难。我不知道它是否是最佳算法，以利用在实践。)

Answer 2

你有没有试过一个贪婪的alg?按点数/价值和地方框中，如果可能的。如果有任何例外im失踪想看到他们。