首页 > 代码库 > 0-1 背包最优子结构
0-1 背包最优子结构
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,选择一个最小值作为属于最优解的元素。
0-1 背包最优子结构