关于装配线的递归求解（dp）

ID:107189 · 发表于 2016-3-5 18:34

#include<stdio.h>
int s[2];
int l[7]={0};
int c[2][8]={{4,8,5,6,4,5,7,2},{2,7,9,3,4,8,4,3}};
int m[2][6]={{0,2,1,2,2,1},{0,2,3,1,3,4}};
int f[2][7]={0};
int fastway(int j,int i);
int fastway(int j,int i)
{
  int a=0;
  int b=0;
  if(f[i][j]!=0)
   return f[i][j];
  if(j==1)
  {
s[1]=c[1][j-1]+c[1][j];
s[0]=c[0][j-1]+c[0][j];
if(i==1)
   return s[1];
if(i==0)
   return s[0];
  }

  if(i==1)
  {
//if(f[1][j]!=0)
// return f[1][j];

a=fastway((j-1),1)+c[1][j];
b=fastway((j-1),0)+m[0][j-1]+c[1][j];

if(a<b)
{
   s[1]=a;
   l[j-1]=1;
   f[1][j]=a;
}
else
{
   s[1]=b;
   l[j-1]=0;
   f[1][j]=b;
}
  }
  if(i==0)
  {
//if(f[0][j]!=0)
//  return f[0][j];
a = fastway((j-1),0)+c[0][j];
b = fastway((j-1),1)+m[1][j-1]+c[0][j];

if(a<b)
{
   s[0]=a;
   l[j-1]=0;
   f[0][j]=a;
}
else
{
   s[0]=b;
   l[j-1]=1;
   f[0][j]=b;
}
  }
  if(i==1)
   return s[1];
  if(i==0)
   return s[0];
}
int main(int agc,char *agv[])
{
  int i;
  int j=7;
  int temp1=fastway(6,0);
  l[6]=0;
  temp1=temp1+c[0][7];
  for(i=1;i<j;i++)
printf("%d ",l[i]);
  printf("%d\n",temp1);

  int temp2=fastway(6,1);
  temp2=temp2+c[1][7];
  l[6]=1;
  for(i=1;i<j;i++)
printf("%d ",l[i]);
  printf("%d\n",temp2);
  return 0;
}

帐号		自动登录	找回密码
密码			立即注册