10-2.cpp

贪婪算法解决背包问题

#include <iostream.h>
const int MIN=100,MAX=20;
int V[MAX][MAX]={0},X1[MAX][MAX]={0},X2[MAX][MAX]={0};

int greedy1(int (*V)[MAX],int N){
	//方案1:为每一个工人分配一个需要工时最少的作业
	int min,flag,k,sum=0;
	for(int i=0;i<N;i++){
		min=MIN;flag=-1;
		for(int j=0;j<N;j++){
			k=i-1;
			while(X1[k][j]!=1&&k>=0) k--;
			if(k<0){
				if(V[i][j]<min){
					min=V[i][j];
					flag=j;
				}
			}
		}
		X1[i][flag]=1;
		sum+=V[i][flag];
	}
	return sum;
}

int greedy2(int (*V)[MAX],int N){
	//方案2:为每一个作业分配一个做的最快的工人
	int min,flag,k,sum=0;
	for(int j=0;j<N;j++){
		min=MIN;flag=-1;
		for(int i=0;i<N;i++){
			k=j-1;
			while(X2[i][k]!=1&&k>=0) k--;
			if(k<0){
				if(V[i][j]<min){
					min=V[i][j];
					flag=i;
				}
			}
		}
		X2[flag][j]=1;
		sum+=V[flag][j];
	}
	return sum;
}

void main(){
	int N; 
	cout<<"N = "; cin>>N;
	cout<<"输入矩阵V[i][j],分配工人i做作业j所需的工时:"<<endl;
	for(int i=1;i<=N;i++) cout<<"	"<<i;
	cout<<endl;
	for(i=1;i<=N;i++){
		cout<<i<<"	";
		for(int j=0;j<N;j++) cin>>V[i-1][j];
	}
	cout<<"方案1:为每一个工人分配一个需要工时最少的作业"<<endl;
	cout<<"X[i][j]"<<endl;
	int sum1=greedy1(V,N);
	for(i=1;i<=N;i++) cout<<"	"<<i;
	cout<<endl;
	for(i=0;i<N;i++){
		cout<<i;
		for(int j=0;j<N;j++){
			cout<<"	"<<X1[i][j];
		}
		cout<<endl;
	}
	cout<<"方案2:为每一个作业分配一个做的最快的工人"<<endl;
	cout<<"X[i][j]"<<endl;
	int sum2=greedy2(V,N);
	for(i=1;i<=N;i++) cout<<"	"<<i;
	cout<<endl;
	for(i=0;i<N;i++){
		cout<<i;
		for(int j=0;j<N;j++){
			cout<<"	"<<X2[i][j];
		}
		cout<<endl;
	}
	cout<<"方案1的总时数为:"<<sum1<<endl;
	cout<<"方案2的总时数为:"<<sum2<<endl;
	if(sum1<sum2) cout<<"方案1比方案2好!"<<endl;
	else if(sum2<sum1) cout<<"方案2比方案1好!"<<endl;
	else cout<<"两个方案一样好!"<<endl;
}


//最佳分配问题假定由N个工人来做N个作业，以求出使总工时数达到最小的分配
//其中限制条件为没有一个工人能分配两项或更多的作业
//程序使用的算法思想是：贪心策略
//程序使用的是两种不同的贪心分配策略，但可知这两种分配算法均不能保证提
//供最优分配