1（一）问题描述：
给定n种物品和一背包。物品i的重量是wi>0，其价值为vi>0，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？ （要求使用回溯法）

2. （二）算法分析：
01背包属于找最优解问题，用回溯法需要构造解的子集树。对于每一个物品i，对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一棵解空间树： 基本思想就是遍历这棵树，以枚举所有情况，最后进行判断，如果重量不超过背包容量，且价值最大的话，该方案就是最后的答案。
在搜索状态空间树时，只要左子节点是可一个可行结点，搜索就进入其左子树。对于右子树时，先计算上界函数，以判断是否将其减去（剪枝）。
上界函数bound():当前价值cw+剩余容量可容纳的最大价值 <= 当前最优价值bestp。
为了更好地计算和运用上界函数剪枝，选择先将物品按照其单位重量价值从大到小排序，此后就按照顺序考虑各个物品。

（三）实验代码：

#include <iostream>  
using namespace std;  
/*
设计算法解0-1背包问题
*/
class Knap  
{friend int Knapsack(int p[],int w[],int c,int n );  
public:		void print()  {  for(int m=1;m<=n;m++)  {  cout<<bestx[m]<<" ";  }  cout<<endl;  };  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)  
{  //为 Knap::Backtrack 初始化  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);  K.print();  delete [] Q;  delete [] K.w;  delete [] K.p;  return K.bestp;  
}  void main()  
{  int *p;  int *w;  int c=0;  int n=0;  int i=0;  cout<<"请输入物品个数："<<endl;   cin>>n;  p=new int[n+1];  w=new int[n+1];  p[0]=0;  w[0]=0;  cout<<"请输入物品的价值："<<endl;  for(i=1;i<=n;i++)cin>>p[i];  cout<<"请输入物品的重量："<<endl;  for(i=1;i<=n;i++)  cin>>w[i];  cout<<"请输入背包容量："<<endl;  cin>>c;  cout<<Knapsack(p,w,c,n)<<endl;  
}