裝配一輛汽車，有兩條裝配線分別有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，代碼人生 閱讀(650)
評論(0) 編輯 收藏