求解0/1背包问题及左右剪枝 回溯法

---

装入背包的物品重量和恰好为W #include<stdio.h> #define MAXN 20 int n,W,k; int w[MAXN],v[MAXN]; int x[MAXN]; int maxv=0; void dfs(int i,int tw,int tv,int rw,int op[]) { if(i>n) { if(tw==W&&tv>maxv) { maxv=tv; int j; 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); } } } int main() { int op[MAXN]; scanf("%d",&n); scanf("%d",&W); for(k=1;k<=n;k++) { scanf("%d",&w[k]); } for(k=1;k<=n;k++) { scanf("%d",&v[k]); } int rw=0; for(k=1;k<=n;k++) { rw+=w[k]; } dfs(1,0,0,rw,op); printf("%d",maxv); return 0; }

---

装入背包的物品重量和不超过W #include<stdio.h> #define MAXN 20 int n,W,k; int w[MAXN],v[MAXN]; int x[MAXN]; int maxv=0; int bound(int i,int tw, int tv) { i++; while(i<=n&&tw+w[i]<=W) { tw+=w[i]; tv+=v[i]; i++; } return tv; } void dfs(int i,int tw,int tv,int rw,int op[]) { if(i>n) { if(tw==W&&tv>maxv) { maxv=tv; int j; 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(bound(i,tw,tv)>maxv) { op[i]=0; dfs(i+1,tw,tv,rw-w[i],op); } } } int main() { int op[MAXN]; scanf("%d",&n); scanf("%d",&W); for(k=1;k<=n;k++) { scanf("%d",&w[k]); } for(k=1;k<=n;k++) { scanf("%d",&v[k]); } int rw=0; for(k=1;k<=n;k++) { rw+=w[k]; } dfs(1,0,0,rw,op); printf("%d",maxv); return 0; }

求解0/1背包问题 回溯法

求解0/1背包问题及左剪枝 回溯法