回溯代码如下，结果并不正确
/*
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);
}
