最小化最大成本

给定N个作业和M个任务，将K个作业分配给其中K < =（min（M，N））的K个任务，以使K个作业中的max_cost最小化。最小化最大成本

你能帮我解决问题的算法吗？我曾试过蛮横的力量，但我不想为大量输入工作。我们可以在这里使用DP吗？

您没有定义'max_cost'或任何类型的成本。 –

maxcost是所有K个工作的最大成本。我们必须为这些K作业找到任务，以便最大程度地减少maxcost –

谢谢我看到了这一点，但我认为我不能修改它以适应我的目的。 –

我使用Hopcroft-Karp Problem解决了类似的问题。首先在所有任务和工作之间找到成本。现在循环查看所有成本，看看是否存在基数为K的二分图。如果存在，那么成本就是答案。如果不移动到下一个成本，并将附加边添加到图中并再次检查，直到您到达基数为K的图。

2014-03-29 04:35:00

您可以通过测试在二分图中存在大小K的匹配来解决问题“是否有最大成本X的解决方案”，其中节点是作业和任务，并且在作业和任务之间存在边缘if执行该任务的工作成本最多为X.您可以使用the Hopcroft-Karp algorithm来表示这是多项式时间。

然后，您可以使用二分查找找到子问题仍然可行的最小X.

2014-02-22 08:13:00

一种可能的方法是通过二分法找出最大成本。

对于给定的最大成本x，当且仅当可以将K作业与K个任务匹配到一个缩减图中K个任务可能完成的情况下，成本> x的所有边都被移除。

您可以使用例如Hopcroft-Karp algorithm测量最大二分配匹配的大小来测试此分配是否可行。

2014-02-22 08:13:16

嘿，好回答！ –

我以为我是安全的，因为它没有一个小时的答案，哦以及:) –

谢谢你的方法工作！ –

回答