0-1背包问题除了耳熟能详的动态规划，还有回溯法和分支限界法
1. 动态规划
使用动态规划，要求原问题具有最优子结构性质，即原问题的最优解包含了其子问题的最优解；并且子问题有重叠的部分，会被重复计算。
0-1背包问题是要求将N个具有一定价值v_i、重量w_i的物品放入承重为C的背包中（放则x_i=1，不放则x_i=0），使得价值最大，即max sum_N(x_i*v_i) s.t sum_N(x_i*w_i)<=C，其子问题可写为将i个具有一定价值v_i、重量w_i的物品放入承重为j的背包中（放则x_i=1，不放则x_i=0），使得价值最大，即max sum_i(x_i*v_i) s.t sum_i(x_i*w_i)<=j。若原问题的最大价值记为c[N][C]，则子问题的最大价值可记为c[i][j]。
动态规划的求解思路是自底向上，即先求解最小的子问题，再基于已经求解的子问题求解下一个子问题的最优解。为了利用已经求解的子问题，可以建一个表来记录。
对于0-1背包问题，可建立如下递归式
主程序如下：
int KnapSack(int n, int w[ ], int v[ ]) { for (i=0; i<=n; i++) //初始化第0列 V[i][0]=0; for (j=0; j<=C; j++) //初始化第0行 V[0][j]=0; for (i=1; i<=n; i++) //计算第i行，进行第i次迭代 for (j=1; j<=C; j++) if (j<w[i]) V[i][j]=V[i-1][j]; else V[i][j]=max(V[i-1][j], V[i-1][j-w[i]]+v[i]); j=C; //求装入背包的物品 for (i=n; i>0; i--){ if (V[i][j]>V[i-1][j]) { x[i]=1; j=j-w[i]; } else x[i]=0; } return V[n][C]; //返回背包取得的最大价值 }
2. 回溯法
回溯法类似深度优先搜索，一股脑往前冲，路走不通了就回头。常用于解决两种问题：寻找满足条件的子集（比如背包问题，x_i=0|1|...），或者排列的方式（比如TSP问题，1234还是2341还是....），根据这两种问题有子集树和排列树两种模板可用。
利用子集树求解0-1背包问题，主要还是如何剪枝。即，在什么情况下会选择不搜索左子树（放弃x_i=1），在什么情况下会选择不搜索右子树（放弃x_i=0）。
当选择x_i=1，背包就会超重时，就会放弃搜索左子树；当选择x_i=0，当前背包的价值和剩余未放入物品（不包括物品i，因为已经选择不放）的价值总和都小于目前最佳价值时，说明已经预测到这个没有前景了==，可以放弃继续搜索右子树了。
主程序如下：
int Bound(int i){ int wr = c - wc; // 背包剩余容量 int vb = vc; // vc为当前背包价值 // 按单位价值递减顺序装入物品 while(i <= n && w[i] <= wr){ wr -= w[i]; vb += v[i]; ++i; } if(i <= n) vb += (v[i]/w[i])*wr; // 继续装满背包 return vb; // 返回背包价值上界 } backtrack(int i){ if( i > n) { // vc当前背包价值，m当前最优价值 m = ( m < vc )? vc : m; output(x); } else { // wc当前背包重量 if ( wc + w[i] <= C ) { // 左子树（将 i 放入背包） x[i]= 1; wc += w[i]; vc += v[i]; backtrack(i+1); x[i]= 0; wc -= w[i]; vc -= v[i]; } if(Bound(i+1) > m){ // 右子树（拿出物品i） backtrack(i+1); } } }
3. 优先队列式分支限界法
分支限界类似广度优先搜索，其原理在《对比Dijkstra和优先队列式分支限界》中已经介绍。
对于0-1背包问题，每个结点的邻接点只有两个，即0和1，记为左子树和右子树。
关键在于什么时候剪枝，即什么情况下不访问左子树，什么情况下不访问右子树，这一点和回溯法类似，判断条件也是一样的。
区别在于：1. 分支限界法要求先对输入物品的单位重量价值做非减排序；2. 分支限界法采用的优先队列式分支限界法，上界值（也就是回溯法用到的Bound(i)）越高排得越靠前。这样做的好处是避免了回溯法的盲目搜索。对于回溯法来说，每次结果都只和最好的目标值进行比较，关注的是结果，而分支限界对每一步都有期待（感觉好励志...）
主程序如下：
while (i != n+1) { // 非叶结点 // 检查当前扩展结点的左儿子结点 Typew wt = cw + w[i]; if (wt <= c) { // 左儿子结点为可行结点 if (cp+p[i] > bestp) bestp = cp+p[i]; AddLiveNode(up, cp+p[i], cw+w[i], true, i+1);} up = Bound(i+1); // 检查当前扩展结点的右儿子结点 if (up >= bestp) // 右子树可能含最优解 AddLiveNode(up, cp, cw, false, i+1); // 取下一个扩展结点（略）}
PS:今晚参加了个就业分享会，大神和学渣齐聚一堂。感受到了人与人之间的差异，以及某种不可言说的命运的力量。以及人生的不可预知性，无法猜测最终的终点和人生轨迹会是什么样，也无法想象身边会有个什么样的人来到。
唯一能做的事，就是做好当下，好好珍惜。