多处理机调度问题
具体问题：设有n个工作，在m个处理机上可以并行运行，每个工作在每个处理机上预测时间都不一样，求最优调度时间，也就是最短时间，（也就是最后一个工作在处理机上停止的截止日期最短）我想的是用动态规划做此题目，但是写着写着就成了回溯了，虽然能达到程序最后目标，但是如果m或者n值增大的话，就程序性能急剧下降了，时间耗费太久了，以下是代码，这个肯定是枚举的了，m，n小还可以，但是增大就不行了，正在尝试用动态规划写，但是有点问题，看有人能做出来不#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;
#define n 3
#define m 2
//int w[n][m]={{6,2,4},{4,7,5},{5,6,6},{9,10,3}};
int matrix[n][m]={{2,5},{3,1},{9,2}};
class node
{
public:
node(int value,int index)
{
this->value=value;
this->index=index;
}
public:
int value;
int index;
};
class Task
{
private:
vector<node> v;
int bestw;
int best[n];
int savex[n];
int *load;
public:
void initTask();
void backtrack(int i);
void printsave();
int getValue(vector<node> v,int number);
};
void Task::initTask()
{
bestw=1000;
int i;
load=new int[m];
for(i=0;i<m;i++)
{
load[i]=0;
}
for(i=0;i<n;i++)
{
best[i]=-1;
}
int j;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}
}
int Task::getValue(vector<node> v,int number)
{
int k;
int value;
for(k=0;k<v.size();k++)
{
node d=v[k];
load[d.index]+=d.value;
}
value=0;
for(k=0;k<m;k++)
{
if(load[k]>value)
{
value=load[k];
}
}
for(k=0;k<m;k++)
{
load[k]=0;
}
return value;
}
void Task::backtrack(int i)
{
if(i==n)
{
int value=getValue(v,i);
if(value<bestw||bestw==-1)
{
int j;
bestw=value;
for(j=0;j<n;j++)
{
savex[j]=best[j];
}
}
return;
}
for(int k=0;k<m;k++)
{
best[i]=k;
node temp(matrix[i][k],k);
v.push_back(temp);
backtrack(i+1);
v.pop_back();
best[i]=-1;
}
}
void Task::printsave()
{
cout<<"最小bestw是:"<<bestw<<endl;
for(int k=0;k<n;k++)
{
cout<<"第"<<k+1<<"任务由第"<<savex[k]+1<<"虚拟机处理"<<endl;
}
}
int main(int argc, char *argv[])
{
Task c1;
c1.initTask();
c1.backtrack(0);
c1.printsave();
system("PAUSE");
return EXIT_SUCCESS;
}
