第3章 动态规划3_0-1背包问题

1、 (Dynamic Programming) 0-1背包问题问题描述： 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？0-1背包问题： 对每种物品i装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。 0-1背包问题(3.4.1) max 1niiixv1. . 0,1,1niiiiw xCstxin 给定给定n n种物品和一背包。物品种物品和一背包。物品i i的重量是的重量是w wi i，其价值为，其价值为v vi i，背包的容量为背包的容量为C C。问。问: :应如何选择装入背包的

2、物品，使得装应如何选择装入背包的物品，使得装入背包中物品的总价值最大入背包中物品的总价值最大? ?0-1背包问题描述背包问题描述:给定给定C 0, w wi i 0, v vi i 0 , 1in.要求找一要求找一n元向量元向量(x1 1,x2 2,xn n), xi i0,1, w wi i xi iC,且且 v vi i xi i达最大达最大, ,即即一个特殊的整数规划问题。一个特殊的整数规划问题。 1.最优子结构性质最优子结构性质 最优子结构性质最优子结构性质:设设(y1,y2,yn)是是 (3.4.1)的一个最优解，则的一个最优解，则(y2,yn)是下面相应子问题的一个最优解是下面相应

3、子问题的一个最优解: niiixv2max112s.t. 0,1, 2niiiiw xCw yxin 证明证明:使用反证法使用反证法. 若不然若不然,设设(z2,z3,zn)是上述子问题的一个最优解是上述子问题的一个最优解,而而(y2,y3,yn)不是它的最优解不是它的最优解.显然有显然有 vizi viyi (i=2,n)且且 w1y1+ wizi C因此因此 v1y1+ vizi (i=2,n) viyi, (i=1,n) 说明说明(y1,z2, z3,zn)是是(3-4-1)0-1背包问题的一个更优解背包问题的一个更优解,导出导出(y1,y2,yn)不是背包问题的最优解不是背包问题的最优

4、解,矛盾矛盾. 2.递归关系递归关系 设所给设所给0-1背包问题的子问题背包问题的子问题(3.4.2) nikkkxvmax nkixjxwtsknikkk,.10 的的最优值为最优值为m(i，j)，即，即m(i，j)是背包容量为是背包容量为j，可选择物品为，可选择物品为i，i+1，n时时0-1背包问题的最优值。背包问题的最优值。 2.递归关系递归关系由由0-1背包问题的最优子结构性质，可以建立计算背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下：的递归式如下： iiiiwjwjjimvwjimjimjim0), 1(), 1(), 1(max),(第第i个物品不装入背包个物品不

5、装入背包第第i个物品装入背包个物品装入背包第第i个物品无法装入背包个物品无法装入背包 (1)( , ) (3.4.4)0 (2)0nnnjwvm n jjw(3.4.3)课本P76有误！ 注注:(3-4-3)式式 此时背包容量为此时背包容量为j，可选择物品为，可选择物品为i。此时在对。此时在对xi作出决策之后作出决策之后,问题处于两种状态之一问题处于两种状态之一:背包剩余容量是背包剩余容量是j,没产生任何效益没产生任何效益;剩余容量剩余容量j-wi,效益值增长了效益值增长了vi .从从n推至推至i+1, i算出最优值算出最优值m(i, j) （ i=n,1） 。 m(1,C)为最优值。为最优值

6、。然后用算法然后用算法traceback找出最优解找出最优解xi ，其中其中i，C为整值。为整值。)3 . 4 . 3( (2) 0(1) ), 1(), 1(), 1(max),(iiiiwjwjjimvwjimjimjim(3.4.4) (2) 0(1) 0),(nnnwjwjvjnm2.递归关系递归关系 3.算法描述算法描述void knapsack( int v, int w, int c, int m) int n = v.length-1; int jMax = min(wn-1, c) /背包剩余容量背包剩余容量/ for(int j = 0; j=jMax; j+) /背包装不

7、下背包装不下wn的情况的情况/ mnj=0; for(int j=wn; j1; i-) jMax=min(wi-1, c); for(int j=0; j=jMax; j+) /背包装不下背包装不下wi的情况的情况/ mij=mi+1j; /没产生任何效益没产生任何效益/ for(int j=wi; j=w1) /如果背包装得下如果背包装得下w1/ m1c=max(m1c, m2c-w1+v1);void traceback(int m, int w, int c, int x) /求最优解求最优解xi / int n = w.length-1; for(int i=1; i0)?1:0;说

8、明说明:当当wi为正整数时，用二维数组为正整数时，用二维数组m来存储来存储m(i,j)相应的相应的最优值。最优值。knapsack算法的算法的一个缺点是要求一个缺点是要求所给物品的重量所给物品的重量w wi i（1 1 i i n n）是整数是整数 )3 . 4 . 3( (2) 0(1) ), 1(), 1(), 1(max),(iiiiwjwjjimvwjimjimjim(3.4.4) (2) 0(1) 0),(nnnwjwjvjnm算法复杂度分析：算法复杂度分析：从从m(i，j)的递归式容易看出，算法的递归式容易看出，算法knapsack需需要要O(nc)计算时间计算时间; traceb

9、ack需需O(n)计算时间计算时间 ；算法总体需要算法总体需要O(nc)计算时间。计算时间。当背包容量当背包容量c很很大时，算法需要的计算时间较多。例如，当大时，算法需要的计算时间较多。例如，当c2n时，算法需要时，算法需要(n2n)计算时间。计算时间。 4.算法复杂度分析算法复杂度分析 0-1背包问题 012345678910 w1=2 v1=61w2=2 v2=32w3=6 v3=53w4=5 v4=44w5=4 v5=65 0问题实例问题实例： 有5个物品，其重量分别是2, 2, 6, 5, 4，价值分别为6, 3, 5, 4, 6，背包的容量为10。 0-1背包问题 012345678

10、910 w1=2 v1=61w2=2 v2=32w3=6 v3=53w4=5 v4=44w5=4 v5=65 0问题实例： 有5个物品，其重量分别是2, 2, 6, 5, 4，价值分别为6, 3, 5, 4, 6，背包的容量为10。0 00 00 00 06 66 66 66 66 66 66 6m5=4=6m5=4=6 0-1背包问题 012345678910 w1=2 v1=61w2=2 v2=32w3=6 v3=53w4=5 v4=44w5=4 v5=65 0问题实例： 有5个物品，其重量分别是2, 2, 6, 5, 4，价值分别为6, 3, 5, 4, 6，背包的容量为10。0 00

11、00 00 06 66 666610100 00 00 00 06 66 66 66 66 66 66 6+v4容量为容量为5 5的背包，考虑是否装入物品的背包，考虑是否装入物品4 4 0-1背包问题 012345678910 w1=2 v1=61w2=2 v2=32w3=6 v3=53w4=5 v4=44w5=4 v5=65 0问题实例： 有5个物品，其重量分别是2, 2, 6, 5, 4，价值分别为6, 3, 5, 4, 6，背包的容量为10。0 00 06 66 69 99 9121212121515151515150 00 03 33 36 66 69 99 99 9101011110

12、 00 00 00 06 66 66 66 66 6101011110 00 00 00 06 66 66 66 66 6101010100 00 00 00 06 66 66 66 66 66 66 6 0-1背包问题统计结果：问题实例： 有5个物品，其重量分别是2, 2, 6, 5, 4，价值分别为6, 3, 5, 4, 6，背包的容量为10。 5改进算法改进算法 为克服以上缺点，引入阶梯函数。利用序偶概念，改进为克服以上缺点，引入阶梯函数。利用序偶概念，改进算法的计算时间复杂性为算法的计算时间复杂性为O(2n )。而当所给物品的重量。而当所给物品的重量wi是是整数时，其计算时间复杂性为整

13、数时，其计算时间复杂性为 （略）（略） 。 动态规划的其他应用实例（略）动态规划的其他应用实例（略） 凸多边形最优三角剖分凸多边形最优三角剖分 多边形游戏多边形游戏 图像压缩图像压缩 电路布线电路布线 流水作业调度流水作业调度 最优二叉搜索树最优二叉搜索树(min,2 )nOnc 总总 结结 动态规划算法适用于解最优化问题。动态规划算法适用于解最优化问题。通常按以下几个步骤设计动态规划算法：通常按以下几个步骤设计动态规划算法：（1 1）找出最优解的性质，并刻画其结构特征；）找出最优解的性质，并刻画其结构特征；（2 2）递归地定义最优值；）递归地定义最优值；（3 3）以自底向上的方式计算出最优值

14、）以自底向上的方式计算出最优值（4 4）根据计算最优值时得到的信息，构造最优解。）根据计算最优值时得到的信息，构造最优解。 总总 结结 动态规划缺陷：动态规划缺陷：（1 1）无一统一标准模型可供应用。利用无一统一标准模型可供应用。利用“最优子结构性质最优子结构性质”得得出递归关系式后，必须结合问题的特点，结合其他数学技巧出递归关系式后，必须结合问题的特点，结合其他数学技巧求解，且无统一处理方法。求解，且无统一处理方法。（2 2）数值求解中，当问题中的状态变量个数太多，由于计算机数值求解中，当问题中的状态变量个数太多，由于计算机存储量及计算速度限制而无法对付存储量及计算速度限制而无法对付“维数障

15、碍维数障碍”。 总总 结结 动态规划的优越之处动态规划的优越之处: :（1 1）易于确定全局解。动态规划方法是一种逐步改善的方法，易于确定全局解。动态规划方法是一种逐步改善的方法，它把原问题化成一系列结构相似的最优化子问题，而每个子它把原问题化成一系列结构相似的最优化子问题，而每个子问题的变量个数比原问题少得多，约束集合也简单得多，故问题的变量个数比原问题少得多，约束集合也简单得多，故较易于确定全局最优。特别当处理离散类型问题时，动态规较易于确定全局最优。特别当处理离散类型问题时，动态规划是求出全局最优化解的唯一方法。划是求出全局最优化解的唯一方法。（2 2）能得一族解，有利分析结果是否有用或

16、进行选择（决策），能得一族解，有利分析结果是否有用或进行选择（决策），且大大节省工作量。且大大节省工作量。（3 3）能利用经验，提高求解效率。动态规划方法反映过程逐段能利用经验，提高求解效率。动态规划方法反映过程逐段演变的前后联系，与实际进程更紧密。演变的前后联系，与实际进程更紧密。（4 4）有广泛应用背景有广泛应用背景 对对 比比 1. 1. 分治法与动态规划主要共同点分治法与动态规划主要共同点: :二者都要求原问题具有最优子结构性质二者都要求原问题具有最优子结构性质, ,都是将原问题分而治都是将原问题分而治之之, ,分解成若干个规模较小分解成若干个规模较小( (小到很容易解决的程序小到很容

17、易解决的程序) )的子问题的子问题. .然后将子问题的解合并然后将子问题的解合并, ,形成原问题的解形成原问题的解. . 2. 2. 分治法与动态规划实现方法分治法与动态规划实现方法: : 分治法通常利用递归求解分治法通常利用递归求解. . 动态规划通常利用动态规划通常利用迭代法自底向上求解迭代法自底向上求解, ,但也能用具有但也能用具有记记忆功能的递归法自顶向下求解（备忘录法）忆功能的递归法自顶向下求解（备忘录法）. . 3. 3. 分治法与动态规划主要区别分治法与动态规划主要区别: : 分治法将分解后的子问题看成相互独立的分治法将分解后的子问题看成相互独立的. . 动态规划将分解后的子问题理解为相互间有联系动态规划将分解后的子问题理解为相互间有联系, ,有重叠有重叠部分部分. . 对对 比比 4. 4. 分治法与动态规划适用条件分治法与动态规划适用条件: : 分治法：原问题具有最优子结构性质的前提下分治法：原问题具有最优子结构性质的前提下, ,分解出的分解出的子问题都绝对相互独立子问题都绝对相互独立. . 动态规划：原问题具有最优子结构性质的前提下动态规划：原问题具有最优子结构性质的前提下, ,分解出分解出的子问题并不相互独立的子问题并不相互独立, ,求解一个子问题可能要用到已经求解求解一个子问题可能要用到已经求