【问题描述】有n个重量分别为{w1，w2，…，wn}的物品，它们的价值分别为{v1，v2，…，vn}，给定一个容量为W的背包。设计从这些物品中选取一部分物品放入该背包的方案，每个物品要么选中要么不选中，要求选中的物品不仅能够放到背包中，而且满足重量限制具有最大的价值。
具体的物品重量及价值如下，背包容量W=6
根据回溯法的思想，可以想到解空间树是一个二叉树，每一层节点对应的是{w1,w2,...,wn}这些物品中的一个是否被选择进入背包，这就对应两种情况，所以这里的解空间树是一个幂集树
数据结构的设计：使用w[n]数组存储每个物品的重量，v[n]数组存储每个物品的价值。变量W表示背包容量
出于对问题的分析，我们先考虑最优解的情况：选中的物品恰好重量和为W，恰好放入背包中
定义函数 dfs(int tw,int tv,int i,int op[]); 解决问题tw是当前层的总重量，tv是当前层的总价值，i是层数，op记录当前层及之前层的操作
这样就一目了然，下面是代码
#include<stdio.h>int w[] = {0,5,3,2,1};int v[] = {0,4,4,3,1};int n = 4;int W = 6;int maxV = 0;int x[5] = {0};// tw是当前的总重量，tv是当前的总价值，i是节点层数 void dfs(int tw,int tv,int i,int op[]){//进行到最后一层 ,i从1开始 if(i > n){if(tw == W && maxV < tv){for(int j = 1;j <= n; j++)x[j] = op[j];}}else{//选择第i个物品 op[i] = 1;dfs(tw+w[i],tv+v[i],i+1,op);//不选择第i个物品 op[i] = 0;dfs(tw,tv,i+1,op);} }int main(){int op[] = {0};dfs(0,0,1,op);for(int i = 1; i<= n; i++){if(x[i] != 0)printf("第%d个物品选择\n",i);}return 0;}
但是这样写会搜索全部的节点，其实有的节点根本不需要搜索，比如如果选择了第一个物品，那么第二个物品肯定不能选择了，因为这两个物品相加重量已经大于W了，然而我们仍然进行了搜索，所以这时候我们需要进行剪枝
左剪枝
左剪枝考虑的就是选择了当前节点之后还有没有必要进行下个节点选择的搜索，我们就需要判断tw+w[i]与W的大小关系，如果前者大于后者，就没有必要再进行搜索了，直接将左边的枝条减掉。
在代码中，仅仅需要一个判断条件即可
if(tw + w[i] <= W){//选择第i个物品 op[i] = 1;dfs(tw+w[i],tv+v[i],i+1,op);}
右剪枝
右剪枝考虑的是不选择当前节点，即使选择剩下的所有节点，是否能满足重量达到W，所以需要考虑tw+rw-w[i]与W的大小关系，rw是剩下的所有物品的重量和，初始情况下等于W
需要对整个函数进行修改，传入rw这个参数，每次向下一层递归的时候rw赋值为rw-w[i]
#include<stdio.h>int w[] = {0,5,3,2,1};int v[] = {0,4,4,3,1};int n = 4;int W = 6;int maxV = 0;int x[5] = {0};// tw是当前的总重量，tv是当前的总价值，i是节点层数 void dfs(int tw,int tv,int rw,int i,int op[]){//进行到最后一层 ,i从1开始 if(i > n){if(tw == W && maxV < tv){for(int j = 1;j <= n; j++)x[j] = op[j];}}else{if(tw + w[i] <= W){//选择第i个物品 op[i] = 1;dfs(tw+w[i],tv+v[i],rw-w[i],i+1,op);}if(tw + rw - w[i]>= W){//不选择第i个物品 op[i] = 0;dfs(tw,tv,rw-w[i],i+1,op);}} }int main(){int op[] = {0};dfs(0,0,12,1,op);for(int i = 1; i<= n; i++){if(x[i] != 0)printf("第%d个物品选择\n",i);}return 0;}
这样就减掉了很多搜索,但是剪枝的节点个数是不确定的，算法的时间复杂度还是O(2^n)，最坏情况下，还是要搜索2^(n+1)-1个节点
现在将问题回归到原本：只要求总重量<=W,这时候右剪枝的策略就行不通了，因为我们可以使得背包不装满。这时候右剪枝需要使用限界函数来判断(之前说过，剪枝函数分为限界函数和约束函数)
此时进行右剪枝，我们可以剪去那些即使加上后面所有的物品，总价值也不会超过maxV的节点，bound(i)=tr+v，tr是当前的总价值，v是剩余的总价值，这个bound(i)就是一个上界，如果上界小于等于maxV，那么就将其剪掉
