我可以使用匈牙利算法查找最高费用吗？

Question

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

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

Answer 1

维基百科说:

如果目标是找到产生最大成本的分配,则可以通过将每个成本替换为减去成本的最大成本来更改问题以适应设置.

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

换句话说:匈牙利人试图尽量减少任务成本.因此,如果您正在寻找最大值,您可以撤消成本:x - > -x.但是,某些实现(不知道是否全部或任何)需要正数.因此,我们的想法是为每个成本添加一个恒定值,以获得正数.此常量值不会改变产生的影响.

Answer 2

正如大卫在评论中所说：

Multiply the cost matrix by -1 for maximization.