这个问题是NP难问题吗？

Question

我正在尝试为这个问题设计一个合理的算法：

假设你有一堆球。每个球至少有一种颜色，但也可以是多色的。每个球上还有一个数字。还有很多只盒子，每只盒子都只有一种颜色。目标是最大化盒子中球上数字的总和，唯一的规则是：

- 为了把一个球放进一个盒子里，它必须至少有盒子的颜色。 - 你只能在每个盒子里放一个球。

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

我已经想出了一些优化方法，可以大大减少运行时间。例如，你可以按点数降序排序球。然后从最高点数到最低点数遍历，如果球只有一种颜色，并且没有其他包含该颜色的更高点数的球，你可以把它放进那个盒子里（从而删除剩余组合中的该盒子和该球）。

我只是好奇是否有某种动态算法可以解决这类问题，或者它只是旅行推销员问题的伪装。如果我知道最多有X种颜色，会有帮助吗？非常感谢任何帮助。谢谢！

简单例子：

球：

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

盒子：

- 1个红 - 1个蓝 - 1个绿

最优解：

- 红球放在红盒子里 - 蓝球放在蓝盒子里 - 绿/蓝球放在绿盒子里

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

- Kenny

---

既然所有球都有一个盒子可以放置，那么所有组织的价值点数都是相同的，对吗？或者我漏掉了什么？ - TaslemGuy

你能详细说明一下“最大化盒子中所有球的数字之和”的目标吗？你是想最大化单个盒子的数字之和吗？你是否总是使用所有可用的球？ - JoshD

你想要优化什么？特定框中的值之和？所有框中的值之和？ - liori

你可能想添加一条注释，说明你只能在盒子里放一个球。 - liori

你应该在开始时清楚地说明一个盒子只能装一个球。 - JoshD

Answer 1

这是加权二分图最大权匹配问题的一个特例。构建一个图，左侧顶点对应于球，右侧顶点对应于盒子，连接球和盒子的边的权重为V，其中V是球上的数字，如果球不能放入盒子，则为0。添加额外的盒子或球并连接到另一侧，边的权重为零，直到每一侧都有相同数量的顶点。您要寻找的任务由结果图中非零权重的边的集合确定（即最大总权重匹配）。

使用匈牙利算法可以在O(n^3)时间内解决分配算法，其中n是球或盒子数量的最大值。（顺便说一下，我提到匈牙利算法只是因为它是我熟悉的理论结果，而且它可能回答了原问题是否NP难的标题问题。我不知道它是否是实践中使用的最佳算法。）

- Reid Barton

---

另一个链接：http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipartite_graphs - sdcvvc

哇，这看起来非常有前途！我需要一些时间来消化它并尝试实现它，但非常感谢你！ - Kenny

让我试着更进一步……假设第一个目标是最大化放置在盒子中的球的数量，然后决胜者将是最大总和。这仍然可以在多项式时间内解决吗？ - Kenny

负的边权值不应该影响解决最大权匹配问题的算法。即使它们有影响，您也可以通过为每个边权值添加足够大的常数，将具有负边权值的最大权匹配问题实例转换为具有非负权值和相同最优匹配的实例。(续) - Reid Barton

谢谢Reid，我发表了那条评论后就意识到了负边权的问题，所以我删除了它并重新表达了我的问题（在你的评论上方）。 - Kenny

是的，在这种情况下，您可以将所有边权为0的边权更改为-C，其中C是足够大的常数，具体来说，大于所有球权重的总和。然后，最大权匹配首先是具有最少权重为-C的边的匹配，即最大基数匹配，其次是在这些匹配中具有正边上最大总权重的匹配。 - Reid Barton

Answer 2

你尝试过贪心算法吗？ 按点数/价值排序并尽可能放置在盒子里。 如果有任何我忽略的异常情况，我想看到它们。

- Anders

---

假设你有一个价值10分的红/绿色球和一个价值5分的红色球。你有一个绿盒子和一个红盒子。使用贪心算法，你首先把红/绿色球放在红盒子里，然后你无法把红色球放在任何地方:( - Kenny

是的，但我认为你错了。当使用贪心算法时，您可以将红/绿球放置在绿色框中，如何处理更多选项取决于您。贪心只想让您在放置5分球之前先放置10分球。 - Anders

如果你必须考虑未来的走法，那将需要大量额外的工作，而贪心算法以它们的效率而闻名。贪心算法是高效的，因为像找零一样，它们能够完全忽略未来，只需在本轮中做出任何可能提供最高奖励的选择即可。 - Olathe