给定 N 个工作和 M 个任务，将 K 个工作分配给 K 个任务，其中 K<=(min(M,N))，以便 K 个工作中的 max_cost 最小化。
你能帮我解决这个问题的算法吗？我尝试过蛮力，但我不适合大量输入。我们可以在这里使用 DP 吗？
最佳答案
您可以通过测试二分图中是否存在大小为 K 的匹配来解决“是否存在最大成本为 X 的解决方案”的问题，其中节点是作业和任务，如果作业和任务之间存在边完成该任务的工作成本最多为 X。您可以使用 the Hopcroft-Karp algorithm为此，这是多项式时间。
然后您可以使用二分查找找到子问题仍然可行的最小 X。
关于algorithm - 最小化最大成本，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21951100/