流水作业调度问题.cpp

动态规划解一系列经典问题

//? 流水作业调度问题

#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#define N 10

void Sort(int n, int b[])
{
}

int FlowShop(int n, int a[], int b[], int c[])
{
	class Jobtype {
	public:
		int operator<=(Jobtype a) const
		{ return (key<=a.key); }
		int key, index;
		bool job;
	};
	Jobtype *d=new Jobtype[n];
	for(int i=0; i<n; i++)
	{
		d[i].key=a[i]>b[i] ? b[i] : a[i];
		d[i].job=a[i]<=b[i];
		d[i].index=i;
	}
	Sort(n, b);
	int j=0, k=n-1;
	for(i=0; i<n; i++)
	{
		if(d[i].job) c[j++]=d[i].index;
		else c[k--]=d[i].index;
	}
	j=a[c[0]];
	k=j+b[c[0]];
	for(i=1; i<n; i++)
	{
		j+=a[c[i]];
		k=j<k ? k+b[c[i]] : j+b[c[i]];
	}
	delete d;
	return k;
}

void main()
{
	srand(time(0));
	int a[N], b[N], c[N];
	FlowShop(N, a, b, c);
}