大漠落日

while(!dead) study++;
posts - 46, comments - 126, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

算法复习之动态规划装配站问题

Posted on 2011-06-28 15:57 乱78糟 阅读(440) 评论(0)  编辑 收藏 引用 所属分类: 算法&数据结构
/***********************************
*    动态规划之装配线问题
*    yanzh 2011-6-27
***********************************
*/
#include 
<iostream>
using namespace std;

#define NUM    6
#define LINE 2

//装配线每个装配站装配开销
int a[LINE][NUM] = { {7,9,3,4,8,4}, {8,5,6,4,5,7} };
//换线时的移动时间开销
int t[LINE][NUM] = { {2,3,1,3,4,0}, {2,1,2,2,1,0} };
//每条装配线每个装配站的最优解
int f[LINE][NUM] = { 0 };
//最后的最快方案
int l[LINE][NUM] = { 0 };

//e表示移动到装配线时间
int e[LINE] = { 2,4 };
//x表示离开装配线时间
int x[LINE] = { 3,2 };

//最快时间
int fast = 0;
//最快的线
int line = 0;

void print(int i, int j)
{
    
if (j == 0)
    {
        
return;
    }
    
else
    {
        i 
= l[i][j];
        print(i, j
-1);
    }

    cout
<<"线"<<i<<",站"<<j-1<<",时间"<<f[i][j-1]<<endl;
}

void output()
{
    cout
<<"最快路线:"<<fast<<endl;
    print( line, NUM );
}


//迭代
void fastest_way(int n)
{
    f[
0][0= a[0][0+ e[0];
    f[
1][0= a[1][0+ e[1];

    
for (int j = 1; j < n; j++)
    {
        
//从第一条线进入
        if ((f[0][j-1+ a[0][j]) <= (f[1][j-1+ t[1][j-1+ a[0][j]))
        {
            f[
0][j] = f[0][j-1+ a[0][j];
            l[
0][j] = 0;    //第一条线快些
        }
        
else
        {
            f[
0][j] = f[1][j-1+ t[1][j-1+ a[0][j];
            l[
0][j] = 1;    //第二条线快些
        }

        
//从第二条线进入
        if ((f[1][j-1+ a[1][j]) <= (f[0][j-1+ t[0][j-1+ a[1][j]))
        {
            f[
1][j] = f[1][j-1+ a[1][j];
            l[
1][j] = 1;
        }
        
else
        {
            f[
1][j] = f[0][j-1+ t[0][j-1+ a[1][j];
            l[
1][j] = 0;
        }
    }

    
if ((f[0][n-1+ x[0]) <= (f[1][n-1+ x[1]))
    {
        fast 
= f[0][n-1+ x[0];
        line 
= 0;
    }
    
else
    {
        fast 
= f[1][n-1+ x[1];
        line 
= 1;
    }
}

int main()
{
    fastest_way(NUM);

    output();

    
return 0;
}

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理