c++ - 求最小值

Question

我无法理解如何解决这个问题。有人可以帮助我指出我的前进方向吗？
给出了N 个任务，并且有 M 个工作线程可用。每个 worker 可以花费不同的时间来完成每个任务。给出了每个 worker 完成每个任务所需的时间。在任何时候，只有一名 worker 只能完成一项任务。但是条件是 worker 一旦停止工作，就不能再从事任何任务。我想找出完成所有任务所需的最少时间。这是一个例子-
M = 3
N = 4 {T1，T2，T3，T4}
每个工作人员(Wi)完成每个任务(Ti)所需的天数-

有很多方法可以完成任务，其中一些是-

所有任务均由W1完成===>花费的总时间= 1 + 2 + 2 + 3 = 8

所有任务均由W2完成===>花费的总时间= 3 + 1 + 3 + 2 = 9

所有任务均由W3完成===>总花费时间= 1 + 1 + 6 + 6 = 14

W1完成的T1，T2，T3和W2完成的T4 ===>花费的总时间= 1 + 2 + 2 + 2 = 7

W1完成的T1，T2和W3完成的T3，T4 ===>花费的总时间= 1 + 2 + 6 + 6 = 15

由W3完成的T1，T2，由W1完成的T3和由W2完成的T4 ===>花费的总时间= 1 + 1 + 2 + 2 = 6

还有更多可能的方法，但是花费最少时间的方法是第六种方法(也如下图所示)。

当 worker 人数只有2时，我才能够理解该怎么做。

#include<iostream>
using namespace std;

int N=4,M=2;

int main()
{   
    int i,j,min=INT_MAX;
    
    int sum,sum1;
    
    int w0[N] = {1,2,2,3};
    int w1[N] = {3,1,3,2};
    
    for(i=0;i<N;i++)
    {
        sum=0;
        sum1=0;
        for(j=0;j<i;j++)
        {
            sum+=w0[j];
            sum1+=w1[j];
        }
        for(j=N-1;j>=i;j--)
        {
            sum+=w1[j];
            sum1+=w0[j];
        }
        
        if(sum<sum1)
        {
            if(min>sum)
                min = sum;
        }
        else
        {
            if(min>sum1)
                min = sum1;
        }
    }
    
    cout<<min;
    
    return 0;
}

我试图用下面的另一个表来解释它-

但是这样我只能找到2个 worker 的最小值。我需要帮助来了解2位以上 worker 的方法。
为此也可能有DP解决方案吗？

Answer 1

我认为可以解决此问题的最佳方法是使用递归。我将通过为每个调用传递一个不可用的工作程序列表和一个运行总和以及一个最小值的全局变量来实现这一点。
如果您有一个值矩阵，这也将是最好的。就像matrix[0] = {1, 2, 3}; matrix[1] = {3, 4, 5}一样。我已经有一段时间没有对矩阵进行硬编码了，所以如果语法有点差，请原谅我。
因此，使用全局变量作为矩阵，这看起来像

int matrix[m][n];
int runningMinimum = INT_MAX; //set the runningMinimum to max so any value compared will be lower
void minimum(int i, vector<int> bannedWorkers, int currentWorker, int sum){
    //test the end condition here
    if (i == n-1){//last column
        if (sum < runningMinimum){runningMinimum = sum;}
        return; //we want to return at the end, whether it's found the new lowest value or not
   
    //if we're not at the end, we need to move one step to the right for all possible workers
    for (int j = 0; j < m; j++){//For each worker
        
        //check to see if the worker is no longer allowed to work
        bool isBanned = false
        for (int k = 0; k < bannedWorkers.size(); k++){
            if (bannedWorkers[k] == j) isBanned = true;
        }
        if(!isBanned){
            if (j == currentWorker){
                minimum(i+1, bannedWorkers, currentWorker, sum+matrix[j][i])
            }else{
                vector<int> newBannedWorkers = bannedWorkers; //Make sure to copy to a new vector
                newBannedWorkers.push_back(currentWorker);
                minimum(i+1, newBannedWorkers, j, sum + matrix[j][i])
            }
        }
    }
    return; //after we've checked every option we want to end that call
}

这是一个未经检验的粗略想法，但它应该为您提供一个坚实的起点。希望能帮助到你!