abcd.rar_greedy knapsack_knapsack c_背包问题 贪婪_贪婪_贪婪算法

#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个作业，以求出使总工时数达到最小的分配 //其中限制条件为没有一个工人能分配两项或更多的作业 //程序使用的算法思想是：贪心策略 //程序使用的是两种不同的贪心分配策略，但可知这两种分配算法均不能保证提 //供最优分配