求最小值 [英] Finding the minimum value
问题描述
我无法理解如何解决这个问题.有人可以帮助我指出我该如何做的方向吗?
I can't begin to understand how to approach this problem. Can someone help me to just point me in the direction as to how I can approach it?
N 个任务，并且有 M 个工作器可用.每个工人可以花费不同的时间来完成每个任务.给出了每个工人完成每项任务所花费的时间.在任何时候，只有一名工人才能完成一项任务.但是条件是工人一旦停止工作，就不能再从事任何任务.我想找出完成所有任务所需的最短时间是多少.这是一个例子-
N tasks are given and there are M workers that are available. Each worker can takes different times to complete each task. The time taken by each worker for every task is given. At any time only one task can be worked on by only one worker. But the condition is once a worker has stopped working, he can't work on any task again. I want to find out what is the minimum time required to finish all the tasks. Here's an example-
M = 3
N = 4 {T1，T2，T3，T4}
每个工作人员(W i )完成每个任务(T i )-
M = 3
N = 4 {T1, T2,T3,T4}
No of days required by each worker (Wi) for each task (Ti) -
完成任务有很多方法，其中一些是-
There are many ways to finish the task, some of them are -
- 所有任务均由W1 ===>完成.总耗时= 1 + 2 + 2 + 3 = 8
- 所有任务均由W2 ===>完成.总耗时= 3 + 1 + 3 + 2 = 9
- 所有任务均由W3完成===>总耗时= 1 + 1 + 6 + 6 = 14
W 1完成的T 1，T 2，T 3和W 2完成的T 4 ＝＝＝>总耗时= 1 + 2 + 2 + 2 = 7
由W1完成的T1，T2和由W3完成的T3，T4 ＝＝＝>.总耗时= 1 + 2 + 6 + 6 = 15
T1，T2由W3完成，T3由W1完成，T4由W2完成.总耗时= 1 + 1 + 2 + 2 = 6
- All the tasks are done by the W1 ===> total time taken = 1+2+2+3 = 8
- All the tasks are done by the W2 ===> total time taken = 3+1+3+2 = 9
- All the tasks are done by the W3 ===> total time taken = 1+1+6+6 = 14
- T1,T2,T3 done by W1 and T4 done by W2 ===> total time taken = 1+2+2+2 = 7
- T1,T2 done by W1 and T3,T4 done by W3 ===> total time taken = 1+2+6+6 = 15
- T1,T2 done by W3, T3 done by W1 and T4 done by W2 ===> total time taken = 1+1+2+2 = 6
还有更多可能的方法，但是花费最少时间的方法是第六种方法(也如下图所示).
There are more possible ways but the one that gives the smallest time taken is the 6th one (also shown in the picture below).
当工人人数只有2个时，我才能够理解该怎么做.我是这样做的-
I was just able to understand how to do it when the number of workers are only 2. I did it this way -
#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;
}
我试图用下面的另一个表来解释它-
I tried to explain it using another table below -
但是这样一来，我只能找到2个工人的最小值.我需要帮助来了解两名以上工人的做法.
But this way I can only find min value for 2 workers. I need help to to understand the approach for more than 2 workers.
为此也可以有一个DP解决方案吗?
Can there also be a DP solution possible for this?
推荐答案
我认为解决此问题的最佳方法是使用递归.我将通过为每个调用传递一个不可用的工作程序列表和一个运行总和以及一个最小值的全局变量来实现这一点.
The best way I can think to solve this is using recursion. I would implement this by having a list of unusable workers and a running sum passed to each call, and a global variable of minimum value.
如果您具有值矩阵，这也将最好地工作.就像 matrix [0] = {1,2,3};matrix [1] = {3，4，5} .我有一段时间没有对矩阵进行硬编码了，所以如果语法有点不对，请原谅我.
This would also work best if you had a matrix of values. So like matrix[0] = {1, 2, 3}; matrix[1] = {3, 4, 5}. I haven't hardcoded a matrix in a while so please forgive me if the syntax is a little off.
因此，使用全局变量作为矩阵，这看起来像
So, using global variables for the matrix this would look something like
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
}
这是一个未经验证的粗略想法，但它应该为您提供一个良好的开端.希望对您有帮助！
This is a rough, untested idea but it should give you a solid start. Hope it helps!
这篇关于求最小值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
