几种常见的算法源代码C语言版.doc

几种常见的算法源代码C语言版1. 回溯法 (背包问题) #includebool Contains(int t,int n,int x,int weight,int maxweight) int countweight=0; for(int i=1;i=t;i+) countweight+=xi*weighti; if(countweightn) int countvalue=0; for(int i=1;i=n;i+) countvalue+=xi*valuei; printf(%4d,xi); printf( 总价值为：%drn,countvalue); else for(int i=0;i=1;i+) xt=i; if(Contains(t,n,x,weight,maxweight)&Bound() Backtrack(t+1,n,x,weight,value,maxweight); void main()int n,maxweight,a50,weight50,value50; printf(请输入物品的总个数：); scanf(%d,&n);printf(rn请分别输入%d个物品的重量：rn,n);for(int i=1;i=n;i+) scanf(%d,&weighti); printf(请分别输入%d个物品的价值：rn,n);for(int j=1;j=n;j+) scanf(%d,&valuej); printf(请输入背包所能容纳物品的最大重量：);scanf(%d,&maxweight);printf(rn);Backtrack(1,n,a,weight,value,maxweight); 2. 全排列 (未考虑重复元素)#includevoid Swap(int &a,int &b)int temp;temp=a;a=b;b=temp;void Perm(int num,int k,int m) if(k=m) for(int i=0;i=m;i+)printf(%4d,numi);printf(n);elsefor(int i=k;i=m;i+) Swap(numk,numi); Perm(num,k+1,m); Swap(numk,numi);void main()int a100;printf(请输入要进行全排列的个数：rn);int n;scanf(%d,&n); for(int i=0;in;i+)ai=i+1;printf(%d个数的全排列如下：rn,n);Perm(a,0,n-1);3. 全排列 (考虑重复元素)#includevoid Swap(int &a,int &b) int temp;temp=a;a=b;b=temp;void Perm(int num,int k,int m) if(k=m) for(int i=0;i=m;i+) printf(%4d,numi); printf(rn);else for(int i=k;i=m;i+) if(numi=numk&i!=k) continue; else Swap(numi,numk); Perm(num,k+1,m); Swap(numi,numk); void main()int a5;int m,n;printf(请输入要进行全排列的数的个数（不能超过5）：rn);scanf(%d,&m);printf(请输入%d个整数（可重复）：rn,m);for(int i=0;im;i+)scanf(%d,&n);ai=n;Perm(a,0,m-1); 4. 组合（递归实现）#includevoid PrintComposition(int source,bool templete,int n) for(int i=0;in;i+) if(templetei=true) printf(%3d,sourcei); printf(rn);int count=0;void Composition(int source,bool templete,int n,int m) for(int i=0;im;i+) templetei=true; for(int j=m;jn;j+) templetej=false; PrintComposition(source,templete,n); count+; while(true) for(int i=0;in;i+) if(templetei=true&templetei+1=false)break; if(i=n)return; templetei=false; templetei+1=true; int p=0; while(pi) while(templetep=true)p+; while(templetei=false)i-; if(pi) templetep=true; templetei=false; PrintComposition(source,templete,n); count+; void main() int a5; bool b5; printf(请输入要进行组合的数的个数(不超过5)：rn); int m,n; scanf(%d,&m); /printf(请输入要%d个数：rnm); for(