我正在尝试为这个问题提出一个合理的算法：
假设你有一堆球 . 每个球至少有一种颜色，但也可以是多色的 . 每个球上都有一个数字 . 还有一堆盒子，每个盒子只有一种颜色 . 目标是最大化框中球的数字总和，唯一的规则是：
-
为了将球放在一个盒子里，它必须至少有一个盒子的颜色
-
你每个盒子里只能放一个球 .
例如，您可以将蓝色和绿色球放入蓝色框或绿色框中，但不能放入红色框中 .
我已经提出了一些在运行时间方面有很大帮助的优化 . 例如，您可以按点值的降序对球进行排序 . 然后，当你从最高数字到最低数字，如果球只有一种颜色，并且没有其他高点球包含那种颜色，你可以把它放在那个盒子里（从而将那个盒子和那个球从剩下的组合） .
我只是好奇是有这种类型的问题的某种动态算法，或者它只是伪装的旅行推销员问题 . 如果我知道最多有X种颜色会有帮助吗？任何帮助是极大的赞赏 . 谢谢！
编辑 - 这是一个简单的例子：
球：
-
1个红球 - 5分
-
1蓝球 - 3分
-
1绿/红球 - 2分
-
1绿/蓝球 - 4分
-
1红/蓝球 - 1分
盒：
-
1红色
-
1蓝色
-
1绿色
最优方案：
-
红球在红色框中
-
蓝色框中的蓝色球
-
绿色/蓝色球在绿色框中
Total value: 12 points (5 + 3 + 4)
2 回答
这是maximum weight matching problem on a weighted bipartite graph的一个特例 . 构造一个左顶点对应于球的图形，其右顶点对应于方框，边缘连接球和一个具有权重V的方框，其中V是球上的数字，如果球可以放在方框中，否则为0 . 添加额外的框或球连接到另一侧，边缘重量为零，直到每侧有相同数量的顶点 . 您要查找的分配由结果图中最大（总）重量匹配的非零权重边集确定 .
分配算法可以在O（n ^ 3）时间内求解，其中n在这里是使用Hungarian algorithm的球或盒数的最大值 . （顺便说一下，我应该做出免责声明，我只提到匈牙利算法，因为这是我碰巧熟悉的理论结果，它可能会回答 Headers 中的问题，即原始问题是否是NP难的 . 我不知道是否是在实践中使用的最佳算法 . ）
你试过一个贪婪的alg吗？按点/值排序，如果可能，放在框中 . 如果有任何异常我缺少id喜欢看到它们 .