蓝色的sky
2016-12-30 12:30
采纳率: 50%
浏览 1.4k
已采纳

流水作业调度能用回溯法解决吗?我写了一个回溯发现并不正确。如果不能用回溯法为什么不能

回溯代码如下,结果并不正确
/*
n个作业{0,1,2,…,n}在2台机器上M1和M2组成的流水线上完成加工。
每个作业加工的顺序都是先在M1上加工,后在M2上加工。在两台机器上加工的时间分别为ai和bi。

目标:确定这n个作业的加工顺序,使得从第一台作业开始加工,到最后一个作业完成加工所需要的时间最少。
输入示例
5
2 5
4 2
3 3
6 1
1 7
输出示例:
19
*/
#include
#define n 5
int M1[n]={2,4,3,6,1};
int M2[n]={5,2,3,1,7};
int tag[n]={0,1,2,3,4};
int time1=0;//在1机器上的时间线
int time2=0;//在2机器上的时间线
int min=1000000;
int path[n];
void swap(int i,int j)
{
int temp=tag[i];
tag[i]=tag[j];
tag[j]=temp;
}
void compute(int h)
{
if(h==n)//到达树的叶子节点
{
//min=min if(min>time2)
{
min=time2;
for(int k=0;k {
path[k]=tag[k];
}
}
return;
}
int temp;
for(int i=h;i {
swap(h,i);
time1+=M1[tag[i]];
temp=time2;
time2=(time2>=time1?time2:time1)+M2[tag[i]];//选取大的时间线作为2机器的执行开始时间
// printf("(%d,%d)\n",time1,time2);
compute(h+1);
time1-=M1[tag[i]];
time2=temp;
swap(h,i);
}
}
int main()
{
compute(0);
for(int h=0;h<n;h++)
{
printf("%d\t",path[h]);
}
printf("\n%d\n",min);
}

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

1条回答 默认 最新

相关推荐 更多相似问题