这个问题NP-hard？

我想为这个问题想出一个合理的算法：这个问题NP-hard？

假设你有一堆球。每个球至少有一种颜色，但也可以是多彩的。每个球上还有一个数字。还有一堆只有一种颜色的盒子。我们的目标是最大限度地提高盒中的球数的总和，唯一的规则是：

，以便放置一个球在一个盒子里，它必须至少有框的颜色
您只能在每个框中放置一个球。

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

我已经想出了一些优化，在运行时间方面有很大帮助。例如，您可以按照点值的降序排列球。然后，当你从最高到最低，如果球只有一种颜色，并且没有其他高点球含有这种颜色，你可以把它放在那个盒子里（并且因此从那个盒子中移除那个盒子和那个球）其余组合）。

我只是好奇是否有这种类型的问题的动态算法，或者如果它只是旅行推销员问题的伪装。如果我知道最多只有X种颜色，会有帮助吗？任何帮助是极大的赞赏。谢谢！

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

球：

1红球 - 5分
1个蓝色球 - 3分
1绿/红球 - 2分
1绿色/蓝色球 - 4分
1红/蓝色球 - 1点

盒：

1红
1蓝
1绿色

最优解：

红球在红色框
蓝色球在蓝色框
绿色/蓝色球在绿色框

总价值：12分（5 + 3 + 4）

来源

2010-10-03 Kenny

由于所有的球都有一个盒子，所有的组织都有相同的分值，对吧？或者我错过了什么？ – TaslemGuy 2010-10-03 00:03:33

您能否详细说明“最大限度地提高箱子中所有人数的总和”。你想最大化一个盒子吗？你总是使用所有可用的球吗？ – JoshD 2010-10-03 00:04:30

你想要优化什么？特定框中的值总和？所有盒子上的数值总和？ – liori 2010-10-03 00:04:51

这是一种特殊情况maximum weight matching problem on a weighted bipartite graph。构建一个图形，其左顶点对应于球，其右顶点对应于框，并且边连接球和具有重量V的框，其中V是如果球可以放置在框中的球上的数字，否则为0 。添加额外的箱子或球，加入到另一边的重量为零的边缘，直到每边有相同数量的顶点。您正在查找的作业由结果图中最大（总）权重匹配中非零权重的边集确定。

使用Hungarian algorithm可以在O（n^3）时间内解决赋值算法，其中n是球或盒的数量的最大值。（顺便说一下，我应该声明我只提到匈牙利算法，因为它是我熟悉的理论结果，它大概回答了原始问题是NP难题的标题中的问题，我不知道无论它是在实践中使用的最佳算法。）

来源

2010-10-03 00:27:15

另一个链接：http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipartite_graphs – sdcvvc 2010-10-03 00:29:30

哇，这看起来很有希望！我需要一些时间来消化这个，并且实际尝试实现它，但是非常感谢你！ – Kenny 2010-10-03 00:39:14

让我试着更进一步......让我们说第一个目标是最大限度地放置在盒子里的球的数量，然后打破平局将是最大的总和。这仍然可以在多项式时间内解决吗？ – Kenny 2010-10-03 01:01:30

你试过了一个贪婪的alg吗？按点/数值排序，如果可能的话放在箱子里。如果有任何异常即时消息id想要看到它们。

来源

2010-10-03 00:29:04 Anders

假设你有一个价值10分的红色/绿色球和5分的红色球。你有一个绿色的盒子和一个红色的盒子。使用贪婪的算法，你首先把红色/绿色的球放在红色的盒子里，然后你不能把红色的球放在任何地方:( – Kenny 2010-10-03 00:44:15

是的，但我相信你的错误。当使用贪婪alg时，您可以将红色/绿色球放在绿色框中，当有更多选项取决于您时，如何选择处理它。贪心只希望你在放置5分球之前放置10分球。 – Anders 2010-10-03 13:10:02

如果您必须考虑将来要做的动作，那么需要大量的额外工作，而贪婪算法以其效率而闻名。贪婪算法是高效的，因为它们像变革一样，能够完全忽略未来，做出任何选择，从而在本回合中获得最高的回报。 – Olathe 2010-10-03 22:35:52

这个问题NP-hard？

回答

相关问题