동적 계획 알고리즘 병렬 작업 스케줄 링 문제 풀이

정성 동화 토론 감사합니다.
 
아무 말 도 하지 않 고 제목 을 달 아 라.
두 대의 프로세서 A 와 B 로 작업 을 처리 하 다.i 번 째 작업 을 기계 A 에 게 맡 길 때 필요 한 시간 은 ai 이 고 기계 B 가 처리 하면 필요 한 시간 은 bi 이다.지금 은 모든 작업 을 한 대의 기계 로 만 처리 할 수 있 고, 모든 기계 가 두 개의 작업 을 동시에 처리 할 수 없다 고 요구한다.동적 계획 알고리즘 을 설계 하여 이 두 기계 가 이 작업 을 처리 하 는 시간 이 가장 짧다.
 
나 는 처음에는 첫 번 째 숙제 를 다 한 후에 야 두 번 째 숙제 를 할 수 있다 고 생각 했 는데 나중에 야 병행 이라는 것 을 깨 달 았 다.
 
아무 말 도 하지 않 습 니 다. 코드, C + 설명 을 올 립 니 다.

#include<iostream>
#include<string>
using namespace std;
int findMax(int a, int b)
{
	if(a > b)
	{
		return a;
	}else
	{
		return b;
	}
}
int findMin(int a, int b)
{
	if(a < b)
	{
		return a;
	}else
	{
		return b;
	}
}
int main()
{
	int N = 6;
	int a[] ={ 2, 5, 7, 10, 5, 2 };
	int b[6] = { 3, 8, 4, 11, 3, 4 };
	int least[6] = {0}; 
	string result[6] = {""};  
	for (int i = 0; i < N; i++)
	{
		least[i] = 99;
	}

	int aSum = 0, bSum = 0;
	for (int i = 0; i < N; i++)
	{
		aSum += a[i];
		bSum += b[i];
	}


    int timeA[6][1000];
	int timeB[6][1000];
	int timeMax[6][1000];
	char who[6][100];
	char tempRlt[100];

	for (int i = 0; i <= a[0]; i++)
	{
		timeA[0][i] = i;
		if (i < a[0])
		{
			timeB[0][i] = b[0];
			who[0][i] = 'b';
		}
		else
		{
			timeB[0][i] = 0;
			who[0][i] = 'a';
		}
		timeMax[0][i] = findMax(timeA[0][i], timeB[0][i]);
	}

	if (a[0] <= b[0])
	{
		least[0] = a[0];
		tempRlt[0] = 'a';
	}
	else
	{
		least[0] = b[0];
		tempRlt[0] = 'b';
	}
	result[0] = string(tempRlt);         

	for (int k = 1; k < N; k++)
	{
		int tempSum = 0;
		for (int temp = 0; temp <= k; temp++)
		{
			tempSum += a[temp];
		}
		for (int i = 0; i <= tempSum; i++)
		{
			timeA[k][i] = i;
			if (i < a[k])
			{
				timeB[k][i] = timeB[k - 1][i] + b[k];
				who[k][i] = 'b';
			}
			else
			{
				if ((timeB[k - 1][i] + b[k]) <= timeB[k - 1][i - a[k]])
				{
					timeB[k][i] = timeB[k - 1][i] + b[k];
					who[k][i] = 'b';
				}
				else
				{
					timeB[k][i] = timeB[k - 1][i - a[k]];
					who[k][i] = 'a';
				}
			}
			timeMax[k][i] = findMax(timeA[k][i], timeB[k][i]);
		}

		for (int i = tempSum + 1; i < aSum; i++)
		{
			timeA[k][i] = tempSum;
			timeB[k][i] = 0;
		}
		int flag = 0;
		for (int i = 0; i <= tempSum; i++)
		{
			if (timeMax[k][i] > 0 && timeMax[k][i] < least[k])
			{
				least[k] = timeMax[k][i];
				flag = i;
			}
		}
		tempRlt[k] = who[k][flag];
		for (int i = k; i > 0 && flag > 0; i--)
		{
			if (tempRlt[i] == 'a')
			{
				flag -= a[i];
				tempRlt[i - 1] = who[i - 1][flag];

			}
			if (tempRlt[i] == 'b')
			{
				tempRlt[i - 1] = who[i - 1][flag];
			}
		}

		result[k] = string(tempRlt);
	}  

	cout << "  " << N <<"     ：" << result[N-1] << "    " <<least[N-1] << endl;

}