Posted on 2011-06-28 15:57
亂78糟 閱讀(591)
評論(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;
}