jobdispatch.c

这是一个字符串快速匹配的算法KMP算法

//利用回溯法进行批处理作业调度
#include <stdio.h>

void backtrace(int);
void swap(int *, int, int);
void print();

//各作业所需的处理时间
int time[][2] = {       //下标从1开始
	{0, 0},
	{2, 1},
	{3, 1},
	{2, 3}
};

//作业数
int num;
//机器1完成处理时间
int f1;
//完成时间和
int f;
//当前最优值
int bestf = 32655;
//当前作业调度
int x[] = {-1, 1, 2, 3};   //下标从一开始
//当前作业最优调度
int bestx[4];
//机器2完成处理时间
int f2[4];

int main(void)
{
	scanf("%d", &num);
	backtrace(1);
	print();
	return 0;
}

void backtrace(int t)
{
	if(t > num)
	{
		int i;
		for(i = 1;i <= num;i++)
			bestx[i] = x[i];
		bestf = f;
	}
	else
	{
		int j = t;
		for(;j <= num;j++)
		{
			f1 += time[x[j]][0];
			printf("f1 = %d ", f1);
			f2[t] = ((f2[t-1] > f1) ? f2[t-1] : f1) + time[x[j]][1];
			f += f2[t];
			if(f < bestf)
			{
				swap(x, t, j);
				backtrace(t+1);
				swap(x, j, t);
			}
			f1 -= time[x[j]][0];
			f -= f2[t];
		}
	}
}

void swap(int *a, int i, int j)
{
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

void print()
{
	printf("bestf = %d\n", bestf);
	int i;
	for(i = 1; i <= num; i++)
		printf("%d ", bestx[i]);
	printf("\n");
}