找到最有效的方法在工人之间分配不同工作任务的算法
Algorithm to find the most efficient way to distribute non-identical work tasks between workers
假设我有一组任务需要完成。我有两个相同的工作人员来处理它们，并且（为简单起见）让我们假设我对任务的复杂性有完美的了解：没有我不知道的任务，而且我确切地知道每个任务需要多长时间完成。 （但不同的任务会花费不同的时间。）每个工人一次只能处理一项任务，一旦开始，必须继续处理直到任务完成。任务之间没有依赖关系，因此必须先完成一个任务才能开始另一个任务。
考虑到这些限制，是否有任何已知的最佳算法来分配两个工人之间的工作，从而最大限度地减少完成所有任务的总时间？一个明显的、幼稚的解决方案是每次一个工人空闲时，总是分配给它最长（或最短）的剩余任务，但是有没有更有效的方法？
这是 partition problem, which is NP-Complete，但是如果任务时间以相对较低的整数给出 - 有一个伪多项式时间动态规划解决方案可以解决它。
在你的例子中，你基本上得到了一组数字——你想将它们分配给两个子集，这样子集的总和就相等（或尽可能接近相等，这是优化变体分区问题）。
DP解的递归公式应该是这样的：
DP[0, 0] = true
DP[0, x] = false | x != 0
DP[i, x] = DP[i-1, x-value[i]] OR DP[i-1, x]
^ ^
assigned i to S1 Assigned i to S2
计算DP[n+1, SUM]需要的所有值（其中SUM是任务总和，n是任务数），你要找的值是DP[n+1, SUM/2] 看看能不能完美完成。
获取每个子集的实际任务是通过追溯您的步骤来完成的，类似于解释的 here。
假设我有一组任务需要完成。我有两个相同的工作人员来处理它们，并且（为简单起见）让我们假设我对任务的复杂性有完美的了解：没有我不知道的任务，而且我确切地知道每个任务需要多长时间完成。 （但不同的任务会花费不同的时间。）每个工人一次只能处理一项任务，一旦开始，必须继续处理直到任务完成。任务之间没有依赖关系，因此必须先完成一个任务才能开始另一个任务。
考虑到这些限制，是否有任何已知的最佳算法来分配两个工人之间的工作，从而最大限度地减少完成所有任务的总时间？一个明显的、幼稚的解决方案是每次一个工人空闲时，总是分配给它最长（或最短）的剩余任务，但是有没有更有效的方法？
这是 partition problem, which is NP-Complete，但是如果任务时间以相对较低的整数给出 - 有一个伪多项式时间动态规划解决方案可以解决它。
在你的例子中，你基本上得到了一组数字——你想将它们分配给两个子集，这样子集的总和就相等（或尽可能接近相等，这是优化变体分区问题）。
DP解的递归公式应该是这样的：
DP[0, 0] = true
DP[0, x] = false | x != 0
DP[i, x] = DP[i-1, x-value[i]] OR DP[i-1, x]
^ ^
assigned i to S1 Assigned i to S2
计算DP[n+1, SUM]需要的所有值（其中SUM是任务总和，n是任务数），你要找的值是DP[n+1, SUM/2] 看看能不能完美完成。
获取每个子集的实际任务是通过追溯您的步骤来完成的，类似于解释的 here。