首页 > 代码库 > 算法导论--装备线调度(升序&&降序输出)
算法导论--装备线调度(升序&&降序输出)
题意就先不用讲了吧,感觉自己还没有掌握核心的东西。
//心得 //怎样保持路径,递归的实现 #include<iostream> #include<cstdio> #include<vector> #include<stack> #include<cstring> using namespace std; int a[100][100];//time for station int t[100][100];//time for from Li to Lj int f[100][100];//recorded time int l[100][100];//keep trace of fastest ways,比如l[1][6]==2,说明l[1][6]是从 //lines 2过来的 int e[2];//into time int ss[100]; int x[2];//depart time int last_time; /*******test data********* 1 6 7 9 3 4 8 4 8 5 6 4 5 7 2 3 1 3 4 2 1 2 2 1 2 4 3 2 *************************/ /********core code******/ int assmbly_line(int m) { int ff; f[1][1]=e[1]+a[1][1]; f[2][1]=e[2]+a[2][1];//开始时比较进入哪一条装配线 // printf("\n%d %d",f[1][1],f[2][1]); for(int j=2;j<=m;j++){//最优化选择 if(f[1][j-1]+a[1][j]<=f[2][j-1]+a[1][j]+t[2][j-1]) { f[1][j]=f[1][j-1]+a[1][j]; l[1][j]=1; // printf("j=%d 1\t",l[1][j]); } else { f[1][j]=f[2][j-1]+a[1][j]+t[2][j-1]; l[1][j]=2; // printf("j=%d 2\t",l[2][j]); } if(f[2][j-1]+a[2][j]<=f[1][j-1]+t[1][j-1]+a[2][j]) { f[2][j]=f[2][j-1]+a[2][j]; l[2][j]=2; // printf("j=%d 2\t",l[2][j]); } else { f[2][j]=f[1][j-1]+t[1][j-1]+a[2][j]; l[2][j]=1; // printf("j=%d 1\t",l[2][j]); } } if(f[1][m]+x[1]<=f[2][m]+x[2]) { int i=1; ff=f[1][m]+x[1]; last_time=1; } else { ff=f[2][m]+x[2]; last_time=2; } return ff; }//打印路径降序 void print_lines(int s[100],int ll,int m) { int i=ll; ss[m]=i;//为了后面的升序使用 printf("lines: %d,stations: %d\n",i,m); for(int j=m;j>=2;j--) { i=l[i][j]; printf("lines: %d,stations: %d\n",i,j-1); ss[j-1]=i; } }//打印路径升序递归 void print_cursion_line( int l[][100],int last_l,int n) { int i=last_l; if(n==1) printf("Lines %d,stations %d\n",i,n); else { print_cursion_line(l,l[i][n],n-1); printf("Lines %d,stations %d\n",i,n); } }//打印路径非递归 void nocursion_increasing(int ss[100],int m) { for(int i=1;i<=m;i++) printf("lines %d,stations %d\n",ss[i],i); } //*******core code******// int main() { int m; freopen("in.txt","r",stdin); int k; scanf("%d",&k);//测试的数据块数 while(k--){ memset(a,0,sizeof(a)); memset(t,0,sizeof(t)); memset(f,0,sizeof(f)); memset(l,0,sizeof(l)); memset(e,0,sizeof(e)); memset(x,0,sizeof(x)); scanf("%d",&m);//装配站的数目 for(int i=1;i<=m;i++) scanf("%d",&a[1][i]); for(int i=1;i<=m;i++) scanf("%d",&a[2][i]); for(int i=1;i<m;i++) scanf("%d",&t[1][i]); for(int i=1;i<m;i++) scanf("%d",&t[2][i]); for(int i=1;i<=2;i++) scanf("%d",&e[i]); for(int i=1;i<=2;i++) scanf("%d",&x[i]); } printf("\n"); int cai=assmbly_line(m); printf("The total cast time is %d\n",cai); int ll=last_time; //以下是打印的路径 printf("decreaing output is \n"); print_lines(l[m],ll,m); printf("Increaing and oncursion output is \n"); nocursion_increasing(ss,m); printf("increaing cursion is \n"); print_cursion_line(l,ll,m); // printf("last_time=%d\n",last_time); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。