几种常见的算ห้องสมุดไป่ตู้源代码 C 语言版
1. 回溯法 (背包问题) #include<stdio.h> bool Contains(int t,int n,int x[],int weight[],int maxweight) { int countweight=0; for(int i=1;i<=t;i++) { countweight+=x[i]*weight[i]; } if(countweight<=maxweight) return true; else return false; } bool Bound() { return true; } void Backtrack(int t,int n,int x[],int weight[],int value[],int maxweight) { if(t>n) { int countvalue=0; for(int i=1;i<=n;i++) { countvalue+=x[i]*value[i]; printf("%4d",x[i]); } printf(" 总价值为：%d\r\n",countvalue); } else { for(int i=0;i<=1;i++) { x[t]=i; if(Contains(t,n,x,weight,maxweight)&&Bound()) Backtrack(t+1,n,x,weight,value,maxweight);
第 5/6 页
scanf("%d",&s); a[i]=s; } printf("请输入要取出来的数的个数(不超过 5)：\r\n"); scanf("%d",&n); Composition(a,b,m,n); }
第
6/6
页
第
4/6
页
void Composition(int source[],bool templete[],int n,int m) { for(int i=0;i<m;i++) templete[i]=true; for(int j=m;j<n;j++) templete[j]=false; PrintComposition(source,templete,n); count++; while(true) { for(int i=0;i<n;i++) { if(templete[i]==true&&templete[i+1]==false)break; } if(i==n)return; templete[i]=false; templete[i+1]=true; int p=0; while(p<i) { while(templete[p]==true)p++; while(templete[i]==false)i--; if(p<i) { templete[p]=true; templete[i]=false; } } PrintComposition(source,templete,n); count++; } } void main() { int a[5]; bool b[5]; printf("请输入要进行组合的数的个数(不超过 5)：\r\n"); int m,n; scanf("%d",&m); //printf("请输入要%d 个数：\r\n"m); for(int i=0;i<m;i++) { int s;
第 1/6 页
} } } void main() { int n,maxweight,a[50],weight[50],value[50]; printf("请输入物品的总个数："); scanf("%d",&n); printf("\r\n 请分别输入%d 个物品的重量：\r\n",n); for(int i=1;i<=n;i++) { scanf("%d",&weight[i]); } printf("请分别输入%d 个物品的价值：\r\n",n); for(int j=1;j<=n;j++) { scanf("%d",&value[j]); } printf("请输入背包所能容纳物品的最大重量："); scanf("%d",&maxweight); printf("\r\n"); Backtrack(1,n,a,weight,value,maxweight); } 2. 全排列 (未考虑重复元素) #include<stdio.h> void 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",num[i]); printf("\n"); }
第 3/6 页
for(int i=k;i<=m;i++) { if(num[i]==num[k]&&i!=k) continue; else { Swap(num[i],num[k]); Perm(num,k+1,m); Swap(num[i],num[k]); } } } } void main() { int a[5]; int m,n; printf("请输入要进行全排列的数的个数（不能超过 5） ：\r\n"); scanf("%d",&m); printf("请输入%d 个整数（可重复） ：\r\n",m); for(int i=0;i<m;i++) { scanf("%d",&n); a[i]=n; } Perm(a,0,m-1); } 4. 组合（递归实现） #include<stdio.h> void PrintComposition(int source[],bool templete[],int n) { for(int i=0;i<n;i++) { if(templete[i]==true) printf("%3d",source[i]); } printf("\r\n"); } int count=0;
第 2/6 页
else { for(int i=k;i<=m;i++) { Swap(num[k],num[i]); Perm(num,k+1,m); Swap(num[k],num[i]); } } } void main() { int a[100]; printf("请输入要进行全排列的个数：\r\n"); int n; scanf("%d",&n); for(int i=0;i<n;i++) a[i]=i+1; printf("%d 个数的全排列如下：\r\n",n); Perm(a,0,n-1); } 3. 全排列 (考虑重复元素) #include<stdio.h> void 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",num[i]); printf("\r\n"); } else {