제15장 동태적 계획의'조립선 스케줄링'

1599 단어
동적 기획 연구의 문제점과 분리법의 차이점: 동적 기획의 하위 문제는 서로 독립된 것이 아니라 교집합이 있다. 즉, 하위 문제가 서로 중첩되는 것이다. 중복적으로 중첩된 하위 문제를 계산하는 것을 피하기 위해 아래에서 위로 교체하는 것을 선택하고 나중에 직접 표를 찾는다.이로써 조립선 스케줄링의 복잡도를 O(2^n)에서 O(n)로 낮추었다.
코드는 다음과 같습니다.
#include <iostream>
using namespace std;


void FastestWay(int (*a)[7],int (*t)[7],int *e,int *x,int n,int (*f)[7],int (*l)[7],int &ff,int &ll)
{
	f[0][1]=e[0]+a[0][1];
	f[1][1]=e[1]+a[1][1];
	
	for(int j=2;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]=1;
		}
		else
		{
			f[0][j]=f[1][j-1]+t[1][j-1]+a[0][j];
			l[0][j]=2;
		}
		
		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]=2;
		}
		else
		{
			f[1][j]=f[0][j-1]+t[0][j-1]+a[1][j];
			l[1][j]=1;
		}
	}
	
	if(f[0][n]+x[0]<f[1][n]+x[1])
	{
		ff=f[0][n]+x[0];
		ll=1;
	}
	else
	{
		ff=f[1][n]+x[1];
		ll=2;
	}
}

void PrintStations(int (*l)[7],int i,int j)
{
	if(j==1)
	{
		cout<<"line "<<i<<" ,station "<<j<<endl;
	}
	else
	{
		int ti=i;
		i=l[i-1][j];
		int tj=j;
		j--;
		PrintStations(l,i,j);
		cout<<"line "<<ti<<" ,station "<<tj<<endl;
	}
}

int main()
{
	int n=6;
	int a[2][7]={{0,7,9,3,4,8,4},{0,8,5,6,4,5,7}};
	int t[2][7]={{0,2,3,1,3,4},{0,2,1,2,2,1}};
	int e[2]={2,4};
	int x[2]={3,2};
	int f[2][7],l[2][7];
	int ff=0,ll=0;
	FastestWay(a,t,e,x,n,f,l,ff,ll);
	PrintStations(l,ll,6);
	//cout<<ff<<" "<<ll;
	system("pause");
}
js 흔 한 배열 방법 및 고급 함수
JS 진수 변환

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage