6

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

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

  • 为了将球放入盒子中，它必须至少具有盒子的颜色
  • 你只能在每个盒子里放一个球。

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

我提出了一些在运行时间方面有很大帮助的优化。例如，您可以按点值的降序对球进行排序。然后当你从最高数字到最低数字时，如果球只有一种颜色，并且没有其他包含该颜色的更高点球，你可以把它放在那个盒子里（然后把那个盒子和那个球从其余组合）。

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

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

球：

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

盒子：

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

最佳解决方案：

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

  • 绿盒中的绿/蓝球

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

4

2 回答 2

12

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

分配算法可以在 O(n^3) 时间内求解，其中 n 是球或盒子数量的最大值，使用匈牙利算法。（顺便说一句，我应该做出免责声明，我只提到匈牙利算法，因为它是我碰巧熟悉的理论结果，它大概回答了标题中原始问题是否是 NP 难的问题。我不知道它是否是实践中使用的最佳算法。）

于 2010-10-03T00:27:15.513 回答
0

你试过贪婪的alg吗？如果可能，按点/值排序并放入框中。如果有任何例外，我想看看他们。

于 2010-10-03T00:29:04.413 回答