匈牙利算法在多项式时间内解决了分配问题。给定工人和任务，以及一个包含将每个工人分配给任务的成本的 n×n 矩阵，它可以找到成本最小化的分配。
我想找到成本最高的选择？我可以使用匈牙利语或任何类似的方法吗？或者这只能以指数方式完成？
问问题
6051 次
2 回答
10
维基百科说：
如果目标是找到产生最大成本的分配，则可以通过将每个成本替换为减去成本的最大成本来更改问题以适应设置。
因此，如果我理解正确：在您输入的所有成本中，您会找到最大值。然后将每个成本替换x为max - x。这样你仍然有正成本，你可以运行匈牙利算法。
换种说法：匈牙利试图最小化分配成本。因此，如果您正在寻找最大值，您可以反转成本：x -> -x。但是，某些实现（不知道是全部还是任何）需要正数。因此，我们的想法是为每个成本添加一个常数值，以获得正数。这个常数值不会改变产生的矫揉造作。
于 2013-07-08T07:02:07.860 回答
6
正如大卫在评论中所说：
Multiply the cost matrix by -1 for maximization.
于 2013-07-12T08:53:50.170 回答