標(biāo)題: 關(guān)于裝配線的遞歸求解（dp） [打印本頁(yè)]

---

作者: 51黑tt    時(shí)間: 2016-3-5 18:34
標(biāo)題: 關(guān)于裝配線的遞歸求解（dp）
#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;
}

---

歡迎光臨 (http://www.torrancerestoration.com/bbs/)

Powered by Discuz! X3.1