用回溯法解0_1背包问题时，会用到状态空间树。在搜索状态空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树搜索，否则将右子树剪去。设r是当前剩余物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+r≤bestp时，可剪去右子树。计算右子树中解的上界可以用的方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是右子树中解的上界，用此值来剪枝。

为了便于计算上界，可先将物品依其单位重量价值从大到小排序，此后只要顺序考察各物品即可。在实现时，由MaxBoundary函数计算当前结点处的上界。它是类Knap的私有成员。Knap的其他成员记录了解空间树种的节点信息，以减少函数参数的传递以及递归调用时所需要的栈空间。在解空间树的当前扩展结点处，仅当要进入右子树时才计算上界函数MaxBoundary，以判断是否可以将右子树减去。进入左子树时不需要计算上界，因为其上界与父结点的上界相同。

在调用函数Knapsack之前，需要先将各物品依其单位重量价值从达到小排序。为此目的，我们定义了类Objiect。其中，file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/ksohtml/wps_clip_image-817.png回溯法详解" TITLE="背包问题 回溯法详解" />运算符与通常的定义相反，其目的是为了方便调用已有的排序算法。在通常情况下，排序算法将待排序元素从小到大排序。 

在搜索状态空间树时，由函数Backtrack控制。在函数中是利用递归调用的方法实现了空间树的搜索。具体的代码见《回溯法》文件夹。

程序源码：

#include<iostream>

using namespace std;
#define max(a,b)((a)>(b)?(a):(b))

int bestValue=0;

void backSearch(int *weight,int *value,int capacity,int num,int *mark,int step,int tempValue,int tempWeight)
{
 int i;

 if (step>num)
 {
  if (tempValue>bestValue)
  {
   bestValue=tempValue;
   cout<<bestValue<<endl;
   for (i=1;i<=num;i++)
   {
    cout<<mark[i]<<" ";
   }
   cout<<endl;
  }
  return ;
 }
 else
 {
  if (tempWeight+weight[step]<=capacity)
  {
   mark[step]=1;
   backSearch(weight,value,capacity,num,mark,step+1,tempValue+value[step],tempWeight+weight[step]);
  }
  mark[step]=0;//注意
  backSearch(weight,value,capacity,num,mark,step+1,tempValue,tempWeight);
 }
}

int main()
{
    int capacity,num;
    int *weight,*value,*mark;
    int i;
   
    printf("请输入包的容量：");
    scanf("%d",&capacity);
    printf("请输入物品的数量：");
    scanf("%d",&num);
       
    weight=(int *)malloc(sizeof(int)*(num+1));
    value=(int *)malloc(sizeof(int)*(num+1));
 mark=(int *)malloc(sizeof(int)*(num+1));
 
    for(i=1;i<=num;i++)
    {
  printf("请输入第%d件物品的重量：",i);
  scanf("%d",weight+i);  
  printf("请输入第%d件物品的价值：",i);
  scanf("%d",value+i);
  
  printf("\n");           
    }
 
 backSearch(weight,value,capacity,num,mark,1,0,0);
    printf("书包可容纳的最大价值为：%d\n",bestValue);

    free(weight);
    free(value); 
 free(mark);
 
    system("pause");
    return 0;  
}