1953 - 0-1背包问题（回溯法）
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
编程要求:要求用回法求解.
题目输入
第一行输入物品的个数n和背包容量C。
第二行输入每个物品的价值v[i].
第三行输入每个物品的重量w[i]
题目输出
第一行输出最大价值。
输入/输出样例
题目输入
4 7 9 10 7 4 3 5 2 1
题目输出
20
C语言解答
#include <stdio.h> int n; int w[100]; int v[100]; int c; int result[100]; int a[100]; int max=0; int wcheck() { int i; int wsum=0; for(i=0;i<n;i++) if(a[i]) wsum+=w[i]; return wsum; } int vcheck() { int i; int wsum=0; for(i=0;i<n;i++) if(a[i]) wsum+=v[i]; return wsum; } void f(int N) { int i; if(N>n) { if(vcheck()>max&&wcheck()<=c) { max=vcheck(); } }else for(i=0;i<2;i++) { a[N]=i; f(N+1); } } void main() { int i; scanf("%d",&n); scanf("%d",&c); for(i=0;i<n;i++) scanf("%d",&v[i]); for(i=0;i<n;i++) scanf("%d",&w[i]); f(0); printf("%d\n",max); }
C++解答
#include<iostream> using namespace std; class Knap { friend int Knapsack(int p[],int w[],int c,int n ); private: int Bound(int i); void Backtrack(int i); int c; int n; int *w; int *p; int cw; int cp; int bestp; int *bestx; int *x; }; int Knap::Bound(int i) { int cleft=c-cw; int b=cp; while(i<=n&&w[i]<=cleft) { cleft-=w[i]; b+=p[i]; i++; } if(i<=n) b+=p[i]/w[i]*cleft; return b; } void Knap::Backtrack(int i) { if(i>n) { if(bestp<cp) { for(int j=1;j<=n;j++) bestx[j]=x[j]; bestp=cp; } return; } if(cw+w[i]<=c) { x[i]=1; cw+=w[i]; cp+=p[i]; Backtrack(i+1); cw-=w[i]; cp-=p[i]; } if(Bound(i+1)>bestp) { x[i]=0; Backtrack(i+1); } } class Object { friend int Knapsack(int p[],int w[],int c,int n); public: int operator<=(Object a)const { return (d>=a.d); } private: int ID; float d; }; int Knapsack(int p[],int w[],int c,int n) { int W=0; int P=0; int i=1; Object *Q=new Object[n]; for(i=1;i<=n;i++) { Q[i-1].ID=i; Q[i-1].d=1.0*p[i]/w[i]; P+=p[i]; W+=w[i]; } if(W<=c) return P; float f; for( i=0;i<n;i++) for(int j=i;j<n;j++) { if(Q[i].d<Q[j].d) { f=Q[i].d; Q[i].d=Q[j].d; Q[j].d=f; } } Knap K; K.p = new int[n+1]; K.w = new int[n+1]; K.x = new int[n+1]; K.bestx = new int[n+1]; K.x[0]=0; K.bestx[0]=0; for( i=1;i<=n;i++) { K.p[i]=p[Q[i-1].ID]; K.w[i]=w[Q[i-1].ID]; } K.cp=0; K.cw=0; K.c=c; K.n=n; K.bestp=0; K.Backtrack(1); delete [] Q; delete [] K.w; delete [] K.p; return K.bestp; } int main() { int *p; int *w; int c=0; int n=0; int i=0; cin>>n>>c; p=new int[n+1]; w=new int[n+1]; p[0]=0; w[0]=0; for(i=1;i<=n;i++) cin>>p[i]; for(i=1;i<=n;i++) cin>>w[i]; cout<<Knapsack(p,w,c,n)<<endl; }