首页 > 代码库 > 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 背包最优子结构