lpt.cpp

自己编写的任务机调度问题的近似算法（包括了穷举+近似的算法）

#include <iostream>
#include <algorithm>
const int N  = 50;
using namespace std;

int main()
{
	int n,m;       // n为任务数，m为机器数
	scanf("%d%d",&n,&m);
	int job[N];
	int i,j,k;
	for(i = 0; i < n; i++)
		scanf("%d",&job[i]);
	sort(job,job+n);
	int time[N];         // 用来存储每台机器当前的任务量
	memset(time,0,sizeof(time));
	int num[N];          // 存储每个任务分配的机器编号
	int count = 0;      // 用来存储需要的总时间
	int min;
	for(i = n-1; i >= 0; i--){
		min = time[1];
		k = 1;
		for(j = 2; j <= m; j++)
			if(time[j] < min){
				min = time[j];
				k = j;
			}
		num[i] = k; 
		time[k] += job[i];
	}
	for(i = n-1; i >= 0; i--)
		printf("%d ",num[i]);
	for(j = 1; j <= m; j++)
		if(time[j] > count)
			count = time[j];
	printf("\n%d",count);
}