algorithm - 我可以使用匈牙利算法找到最大成本吗？

Question

匈牙利算法在多项式时间内解决了分配问题。给定 worker 和任务，以及包含将每个 worker 分配给任务的成本的 n×n 矩阵，它可以找到成本最小化的分配。

我想找到成本最大的选择？我可以使用匈牙利语或任何类似的方法吗？或者这只能以指数方式完成？

Answer 1

维基百科说:

If the goal is to find the assignment that yields the maximum cost, the problem can be altered to fit the setting by replacing each cost with the maximum cost subtracted by the cost.

因此，如果我理解正确的话:在您输入的所有成本中，您会找到最大值。然后将每个成本 x 替换为 max - x。这样你仍然有正成本并且你可以运行匈牙利算法。

换句话说:匈牙利语试图最小化分配成本。所以，如果你正在寻找最大值，你可以反转成本:x -> -x。但是，某些实现(不知道是否全部或任何)需要正数。因此，想法是为每个成本添加一个常数值以获得正数。这个常数值不会改变由此产生的影响。