回溯法.c

来自「C++经典算法之 回溯法 常用算法 方便使用」· C语言 代码 · 共 51 行

#include<stdio.h>
#define N 4

int c[N][N];
unsigned int mincost=65535;
int task[N],temp[N],worker[N];

void plan(int k, unsigned int cost)
{
     int i;
     if (k>=N&&cost<mincost)
     {
		 mincost=cost;
		 for (i=0;i<N;i++)
		 {
			 temp[i]=task[i];
		 }
     } 
     else
     {
		 for (i=0;i<N;i++)
		 {
			 if (worker[i]==0&&cost+c[k][i]<mincost)
			 {
				 worker[i]=1;task[k]=i;
				 plan(k+1,cost+c[k][i]);
				 worker[i]=0;task[k]=0;
				 
			 }
		 }
     }
}

void main()
{
	int i,j;
	for (i=0;i<N;i++)
	{
		worker[i]=0;
		task[i]=0;
		temp[i]=0;
		for(j=0;j<N;j++)
			scanf("%d ",&c[i][j]);
	}
	plan(0,0);
	printf("\n最小费用=%d\n",mincost);
	for (i=0;i<N;i++)
	{
		printf("task%d is assigned to Worker%d\n",i,temp[i]);
	}
}