0-1 背包问题描述：
设背包空间为V，有n个物品 x1,x2,...,xn。第i个物品的重量为C[i],价值为W[i]，1<= i <= n。求背包能装下的物品的最大价值。
动态规划解决0-1背包分为4个步骤，
1.最优子结构
2.递归方程
3.略
4.略
1.最优子结构分析：
设解空间为X（x1,...,xj），表示x1……xj是装入背包的物品。
设空间为V背包的一组最优解是 Y( y1,...,ym )。那么 Y-yi一定是V-C[yi]的最优解。如果不是，假设有另一组更优解存在 Z( z1,...zp )。那么可以把这个”剪切“到原”最优解“上。即更优解为： Y'( yi, z1,...zn )。矛盾。
2.假设最优解是Y(y1,...,ym),当前状态是k,v,代表y1....yk的最优解已经放入背包。函数Best(k,v)值等于y1……yk放在背包空间为v的总重。
Best(k,v) = Best( k-1,v-C[yk] ) + W[yk] （1） // 去掉k之后的一个最优解子集，必定是最优的
这个子问题就被转化为了另一个子问题。
寻找最优解：
Best( i,v ) = max{ Best( i-1, v ), Best( i-1, v-C[i] ) + W[i] ) } （2）
------------------------------------------------------------------Done-----------------------------------------------------------
上面的方程(1)我们假定k属于最优解。寻找过程中只有两种情况，如果大于两种情况，我们要判断所有的情况寻找符合最优解的元素，定义它属于最优解。
比如一个问题描述得到的解空间X(x1,...xj)，假定子问题相互独立并且重叠。那么把子问题表示成另一个子问题（最优解S表示成最优解的子集S1+S2，就像（1）方程所述）。在寻找最优解的时候，利用已知矛盾获得。比如（2），最优解一定符合（2）的性质，否则推出矛盾。
在算法导论给选择教室上课的例子里，就是要比较 i<k<j里所有的k，选择一个最小值作为属于最优解的元素。