main.cpp

本程序是麻省理工学院的《算法导论》上的动态规划问题

#include "string.h"
#include "iostream.h"
#include "stdlib.h"
int l[3][50];
int l0,f0;
void fastestway(int n)
{
	int e1,e2,o1,o2;
	int i,j;
	int (*f)[3]=new int[n+1][3];
	int (*b)[3]=new int[n+1][3];
	int (*t)[3]=new int[n][3];
	cout<<"请输入每个站点处所需的时间："<<endl;
	for(j=1;j<=n;j++)
	{
		cout<<"b[1,"<<j<<"]=";
		cin>>b[j][1];
		cout<<"b[2,"<<j<<"]=";
		cin>>b[j][2];
	}
	cout<<"请输入每个站离开配线的时间："<<endl;
	for(j=1;j<n;j++)
	{
		cout<<"t[1,"<<j<<"]=";
		cin>>t[j][1];
		cout<<"t[2,"<<j<<"]=";
		cin>>t[j][2];
	}
	cout<<"每条线的输入输出时间："<<endl;
	cout<<"e1=";
	cin>>e1;
	cout<<"e2=";
	cin>>e2;
	cout<<"o1=";
	cin>>o1;
	cout<<"o2=";
	cin>>o2;
	f[1][1]=e1+b[1][1];
	f[1][2]=e2+b[1][2];
	for(j=2;j<=n;j++)
	{
		if(f[j-1][1]+b[j][1]<=f[j-1][2]+t[j-1][2]+b[j][1])
		{
			f[j][1]=f[j-1][1]+b[j][1];
			l[1][j]=1;
		}
		else {
			f[j][1]=f[j-1][2]+t[j-1][2]+b[j][1];
			l[1][j]=2;
		}
		if(f[j-1][2]+b[j][2]<=f[j-1][1]+t[j-1][1]+b[j][2])
		{
			f[j][2]=f[j-1][2]+b[j][2];
			l[2][j]=2;
		}
		else{
			f[j][2]=f[j-1][1]+t[j-1][1]+b[j][2];
			l[2][j]=1;
		}
	}
	if(f[n][1]+o1<=f[n][2]+o2)
	{
		f0=f[n][1]+o1;
		l0=1;
	}
	else {
		f0=f[n][2]+o2;
		l0=2;
	}
	cout<<"到达每个站点的最快时间："<<endl;
	for(i=1;i<=2;i++)
	{
		cout<<"f("<<i<<","<<"j) ";
		for(j=1;j<=n;j++)
		{
			cout<<f[j][i]<<" ";
		}
		cout<<endl;
	}
}
void output(int i,int j)
{
	if(j==0)
		return;
	output(l[i][j],j-1);
	cout<<"line"<<i<<",station"<<j<<endl;
}
void main()
{
	int n;
	cout<<"请输入装配线的站点个数：";
	cin>>n;
	fastestway(n);
	cout<<"最快通过站点的方式为："<<endl;
	output(l0,n);
}