算法-流水作業調度能用回溯法解決嗎？我寫了一個回溯發現並不正確。如果不能用回溯法為什麼不能

流水作業調度能用回溯法解決嗎？我寫了一個回溯發現並不正確。如果不能用回溯法為什麼不能

回溯代碼如下，結果並不正確
/*
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);
}

最佳回答：

犯了低級錯誤，計算在交換之前