0/1背包问题（回溯法）_回溯法求解0-1背包问题

1.问题分析

        给定n种物品和一个背包容量为c的背包，物品i的重量是wi，其价值为vi，利用回溯法来实现求解如何使装入背包中的物品的总价值最大。

2.算法设计思路

（1）物品有n种，背包容量为C，用v[i]和w[i]存储第i种物品的价值和重量，用x[i]标记第i种物品是否装入背包，用bestx[i]存储第i种物品的最优装载方案；

（2）用递归函数Knapsack（i，bv，bw）来实现回溯法搜索子集树（形式参数i表示递归深度，n用来控制递归深度，形式参数bv和bw表示当前总价值和总重量，bestv表示当前最优总价值）；

（3）若i>n，则算法搜索到一个叶子结点，判断当前总价值是否最优；

（4）若bv>bestv，更新当前最优总价值为当前总价值，再更新装载方案；

（5）采用for循环对物品i装与不装两种情况进行讨论（0≤j≤1）：

          1）x[i]=j；

          2）若总重量不大于背包容量（即bw+x[i]*w[i]<=c），则更新当前总价值和总重量（即bw+=w[i]*x[i]，bv+=v[i]*x[i]）, 对物品                     i+1调用递归函数Knapsack (i+1,cp,cw) 继续进行装载；