装配一辆汽车，有两条装配线分别有n个装配点，每条装配线在进出所花时间为e[i]，x[i] (i=0,1),
每个装配点所需时间a[i][j](i=0,1;j=0,1,...,n-1),从一条装配线i的第j个装配点到另一条装配线的第j+1个装配点所需时间t[i][j]。
首先应找到最佳线路的递归解为：
f1[j]=min(f1[j-1]+a1[j],f2[j-1]+t2[j-1]+a1[j])
f2[j]=min(f2[j-1]+a2[j],f1[j-1]+t1[j-1]+a2[j])
#include<stdio..h>
//装配线
int fastWay(int a[][6],int t[][5],int e[],int x[],int n)//hanshubianliang
{
int f1[6];//=new int[n];
int f2[6];//=new int[n];
int l1[6];//=new int[n];
int l2[6];//=new int[n];
int fmax=0;
int l;
int i,j;
f1[0]=a[0][0]+e[0];//guihua ;
f2[0]=a[1][0]+e[1];
for(j=1;j<n;j++)//DP;
{
if(f1[j-1]+a[0][j]>=f2[j-1]+t[1][j-1]+a[0][j])
{
f1[j]=f2[j-1]+t[1][j-1]+a[0][j];
l1[j]=2;
}
else
{
f1[j]=f1[j-1]+a[0][j];
l1[j]=1;
}
if(f2[j-1]+a[1][j]>=f1[j-1]+t[0][j-1]+a[1][j])
{
f2[j]=f1[j-1]+t[0][j-1]+a[1][j];
l2[j]=1;
}
else
{
f2[j]=f2[j-1]+a[1][j];
l2[j]=2;
}
}
if(f1[n-1]+x[0]>=f2[n-1]+x[1])
{
fmax=f2[n-1]+x[1];
l=2;//JILU SUOXUANDE XIANG L1||L2
}
else
{
fmax=f1[n-1]+x[0];
l=1;
}
for(i=1;i<n;i++)
{
if(l=1)
{
printf("%d ",l1[i]);
}
else if(l=2)
{
printf("%d ",l2[i]);
}
}
return fmax;
}
int main()
{
int a[2][6]={7,9,3,4,8,4,8,5,6,4,5,7};
int t[2][5]={2,3,1,3,4,2,1,2,2,1};
int x[2]={3,2};
int e[2]={2,4};
int n=6;
int f=fastWay(a,t,e,x,n);
printf("\n%d\n",f);
return 0;
}
posted on 2012-07-12 14:55
天YU地___PS，代码人生 阅读(643)
评论(0) 编辑 收藏