这个问题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难的.我不知道是否是在实践中使用的最佳算法.)