5-13.cpp

工作分配问题的实现 对给定的工作费用

#include "iostream"
using namespace std;

const int N=4;    

int best[N];			//最优解
int d[N];				//第i项工作分配给了d[i]
int M[N][N] = {{5,2,6,9},{1,3,8,7},{2,2,4,6},{7,6,4,2}};	//M[i][j]把工作i分配给第j个人来完成所需的费用 
int min = 9999;    

void swap(int a,int b) {    
    int temp = a;    
    a = b;    
    b = temp;    
}       

void backtrack(int i, int n) {    
    if(i > n){							//如果搜索层数大于n就更新最优分配
        int sum = 0;    
		for(int i=1; i<=n; i++)     
			sum += M[i][d[i]];    
		if(sum < min) {    
			min = sum;    
			for(int i=1; i<=n; i++)    
				best[i] = d[i];    
		}    
	}
    else								
        for(int j=i; j<=n; j++) {    
            swap(d[i], d[j]);    
            backtrack(i+1, n);			//回溯
            swap(d[i], d[j]);			
        }    
}    

void main() {    
	int i;
	for(i=1; i<=N; i++)    
		d[i] = i;    
	
	backtrack(1, N); 
	
	cout<<"最小费用："<<min<<endl;    
}