尽量减少只有两名工人的任务成本

Question

我正在尝试使用PHP创建一个算法，通过选择两名可以尽可能便宜地完成这些任务的工作人员来找出完成一组任务的最佳方法。

假设我有一组X个不同的任务和Y个不同的工作人员。每个工作人员可以完成每个X任务的不同价格。您可以假设我有一张表格，显示每个工作人员和每个任务的工作人员完成任务所需的价格。

我的问题是这样的：给定这样一个表格，我如何找到一套正好两个工人谁可以完成所有的任务以最小的总成本？

Answer 1

这是一个可以使用dynamic programming方法解决的优化问题。您的特殊问题（我相信）属于resource allocation的财务限制。标准问题如knapsack problem也包括在内。

在堆栈溢出中至少有一个question要求使用php解决这些问题。在那篇文章中，有一个关于背包问题的php解决方案的链接。我会从that code开始，并将其变为您需要掌握的特定问题定义。

Answer 2

解决这个问题的一个非常简单的方法是考虑所有可能的两名工人对，然后计算成本，如果这两名工人将所有工作分配到最佳状态。一旦你有了这些价值观，你可以把它们中最小的一个拿到整体最小的成本。

现在，让我们看看如果计算完成所有X任务的总成本（如果您要使用特定的一对工作人员）。从你的问题描述来看，似乎每个工人都没有限制他们能做多少工作，这使得这个问题比许多相关问题要容易得多。直觉是这样的：对于任何任务，你都想把这个任务交给工作人员，而这个工作可以比另一个更便宜。因此，可以通过循环每个任务来找到分摊两个工人之间所有任务的总成本，然后将该任务分配给可以以较少资金完成任务的工人。总的来说，我建议接近这个问题如下。使用double for循环，遍历每一对工人。对于每一对，使用第三个for循环遍历每个任务，计算完成该任务的总成本。最后，如果这一对比迄今为止最知名的一对好，那么更新你的猜测就是这个特定的对。一旦你对每一对工作人员运行这个循环，你就会发现这对能以最低的总价格做到这一点。

由于为O（Y ）对工人和X总的任务，这将在O的（Y X）的时间。

希望这会有所帮助！