《算法设计与分析》--0-1背包问题随笔

1、0-1背包问题定义：给定n种物品和一背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。探究我们怎么选择装入背包的物品使其背包中的总价值最大？

2、思考:我们在装入背包的时候对于要装入的物品i，只有两种情况，即装入和不装入背包。并且我们不能将物品i装入背包多次，也不能只是装入部分的物品i。

3、最优子结构性质:0-1背包问题也是满足最优子结构性质的，我们首先给定C>0,Wi>0,Vi>0,1<=i<=n，其实0-1背包问题是一个特殊的整数规划问题。

      其实我们可以设(y1,y2,y3,..,yn)是0-1背包问题的一个最优解,则(y2,...,yn)是下面相应子问题的一个最优解。

      max(Vi*Xi){2<=i<=n}(意思是求Vi和Xi的乘积的和的最大值，这个范围是i从2到n取值)

 (Wi*Xi){2<=i<=n}(求和)<=C-w1*y1

 Xi属于{0,1},2<=i<=n

如果不是。那么设(Z2,...,Zn)是上述子问题的一个最优解，而(Y2,...,Yn)不是它的最优解。

所以可以知道(Vi*Zi求和)>(Vi*Yi求和)，并且(Y2,...,Yn)不是它的最优解。

这说明(Z1,Z2,...,Zn)是所给0-1背包问题的更优解。