Posted on 2011-06-28 15:57
乱78糟 阅读(559)
评论(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;
}