问题1：装入背包中物品重量和恰好为W
#include<stdio.h> #define MAXN 20 int W=6; int n=4;//4种物品 int w[]={0,5,3,2,1}; int v[]={0,4,4,3,1}; int X[MAXN]; int max=0; void dfs(int i,int tw,int tv,int *op); void Output(); int main() { int op[MAXN]; dfs(1,0,0,op); Output(); return 0; } void dfs(int i,int tw,int tv,int *op) { int j; if(i>n){ if(tw==W&&tv>max){ max=tv; for(j=1;j<=n;j++) X[j]=op[j]; } } else{ op[i]=1; dfs(i+1,tw+w[i],tv+v[i],op); op[i]=0; dfs(i+1,tw,tv,op); } } void Output() { int i; int s=0; printf("最佳方案："); for(i=1;i<=n;i++){ if(X[i]!=0){ s=s+v[i]; printf("%d ",i); } } printf("\n对应物品总价值：%d",s); }优化升级1： 增添限界条件： （对于重量超过W的不再进行选择操作）
void dfs(int i,int tw,int tv,int *op)优化升级2： 增添限界条件： （对于重量不可能超过W的进行排除操作）
#include<stdio.h> #define MAXN 20 int W=6; int n=4;//4种物品 int w[]={0,5,3,2,1}; int v[]={0,4,4,3,1}; int X[MAXN]; int max=0; void dfs(int i,int tw,int tv,int rw,int *op); void Output(); int main() { int op[MAXN]; dfs(1,0,0,11,op); Output(); return 0; } void dfs(int i,int tw,int tv,int rw,int *op) { int j; if(i>n){ if(tw==W&&tv>max){ max=tv; for(j=1;j<=n;j++) X[j]=op[j]; } } else{ if(tw+w[i]<=W){ op[i]=1; dfs(i+1,tw+w[i],tv+v[i],rw-w[i],op); } if(tw+rw-w[i]>=W){ op[i]=0; dfs(i+1,tw,tv,rw-w[i],op); } } } void Output() { int i; int s=0; printf("最佳方案："); for(i=1;i<=n;i++){ if(X[i]!=0){ s=s+v[i]; printf("%d ",i); } } printf("\n对应物品总价值：%d",s); }问题2：装入背包中物品重量和不超过W
#include<stdio.h> #include<malloc.h> #define MAXN 20 typedef struct node { int no;//物品编号 int w;//重量 int v;//价值 int p;//单位重量价值 }Node; int n=4; int W=6; //w[]={0,5,3,2,1}; //int v[]={0,4,4,3,1}; int X[MAXN]; int max=0; void dfs(Node *A,int i,int tw,int tv,int *op); int bound(Node *A,int i,int tw,int tv); void Output(Node *A); int main() { Node A[MAXN]; //Node *p=A; int op[MAXN]; int i; //p=(Node*)malloc(sizeof(Node)*(MAXN-1)); printf("请输入物品的重量：\n"); for(i=1;i<=n;i++){ A[i].no=i; scanf("%d",&A[i].w); } printf("请输入物品对应的价值：\n"); for(i=1;i<=n;i++){ scanf("%d",&A[i].v); } dfs(A,1,0,0,op); Output(A); return 0; } void Output(Node *A) { int i; int s=0; printf("最佳方案："); for(i=1;i<=n;i++){ if(X[i]!=0){ s=s+A[i].v; printf("%d ",i); } } printf("\n对应物品总价值：%d",s); } void dfs(Node *A,int i,int tw,int tv,int *op) { int j; if(i>n){ if(tv>max){ max=tv; for(j=1;j<=n;j++){ X[j]=op[j]; } } else return; } else{ if(tw+A[i].w<=W){ op[i]=1; dfs(A,i+1,tw+A[i].w,tv+A[i].v,op); } if(bound(A,i,tw,tv)>max){ op[i]=0; dfs(A,i+1,tw,tv,op); } } } int bound(Node *A,int i,int tw,int tv) { i++; while(i<=n&&tw+A[i].w<=W){ tw=tw+A[i].w; tv=tv+A[i].v; i++; } if(i<=n)return tv+(W-tw)*A[i].p; else return tv; } #include<stdio.h > #define MAXSIZE 20 int n;//n个物品 int c;//背包的容量为c int w[MAXSIZE];//物品的重量 int p[MAXSIZE];//物品的价值 int x[MAXSIZE]; int max; int maxn[MAXSIZE]; void input1(); void input2(); void dfs(int i,int wi,int pi,int *op); int main() { int op[MAXSIZE]; int i,j; scanf("%d %d",&n,&c); for(i=0; ;i++){ if(n==0&&c==0)break; if(n==0){ scanf("%d %d",&n,&c); i++; maxn[i]=0; break; } input1();//输入物品的重量 input2();//输入物品的价值 dfs(0,0,0,op); maxn[i]=max; scanf("%d %d",&n,&c); } for(j=0;j<i;j++){ printf("%d\n",maxn[j]); } return 0; } //输入物品的重量 void input1() { int i; for(i=0;i<n;i++) scanf("%d",&w[i]); } //输入物品的价值 void input2() { int i; for(i=0;i<n;i++) scanf("%d",&p[i]); } void dfs(int i,int wi,int pi,int *op) { if(i>n-1){ if(wi<=c&&pi>=max){ max=pi+p[i]; } } else{ op[i]=1; dfs(i+1,wi+w[i],pi+p[i],op); op[i]=0; dfs(i+1,wi,pi,op); } } #include<iostream> #include<string.h> #define MAXN 100 #define true 1 #define false 0 using namespace std; int c;//容量为c的背包 int n;//从n个物品中选取装入背包的物品 int w[MAXN];//每件物品i的重量为wi int p[MAXN];//价值为pi int maxw[MAXN]; int maxm; void dfs(int *op,int i,int wi,int pi); int main() { int i,j=1,k; int op[MAXN]; memset(op,0,sizeof(op)); while(1){ cin>>n>>c; if(n==0){ if(c==0)break; else { maxw[j]=0; j++; continue; } } for(i=1;i<=n;i++){ cin>>w[i]; } for(i=1;i<=n;i++){ cin>>p[i]; } dfs(op,1,0,0); maxw[j]=maxm; j++; } for(k=1;k<j;k++)cout<<maxw[k]<<endl; return 0; } void dfs(int *op,int i,int wi,int pi) { if(i>n){ if(pi>maxm&&wi<=c){ maxm=pi; } } else{ op[i]=1; dfs(op,i+1,wi+w[i],pi+p[i]); op[i]=0; dfs(op,i+1,wi,pi); } }在if(i>n) 中，maxm=pi;与maxm=pi+p[i];都可以，因为此时的p[i]=0。
