动态规划之01背包

1、1 学习要点学习要点: :理解动态规划算法的概念。理解动态规划算法的概念。掌握动态规划算法的基本要素掌握动态规划算法的基本要素（1 1）最优子结构性质）最优子结构性质（2 2）重叠子问题性质）重叠子问题性质掌握设计动态规划算法的步骤。掌握设计动态规划算法的步骤。(1)(1)找出找出最优解最优解的性质，并刻划其结构特征。的性质，并刻划其结构特征。(2)(2)递归地定义最优值。递归地定义最优值。(3)(3)以以自底向上自底向上的方式计算出最优值。的方式计算出最优值。(4)(4)根据计算最优值时得到的信息，构造最优解。根据计算最优值时得到的信息，构造最优解。2n动态规划法的定义：在求解问题中，对于动

2、态规划法的定义：在求解问题中，对于每一步决策每一步决策，列出各种，列出各种可能的局部解可能的局部解，再，再依据某种依据某种判定条件判定条件，舍弃那些肯定不能得，舍弃那些肯定不能得到最优解到最优解的局部解，在每一步都经过筛选，的局部解，在每一步都经过筛选，以每一步都是最优解来保证以每一步都是最优解来保证全局全局是最优解。是最优解。n动态规划通常应用于最优化问题，即动态规划通常应用于最优化问题，即做出做出一组选择以达到一个最优解一组选择以达到一个最优解。关键是存储。关键是存储子问题子问题的每一个解，以备它的每一个解，以备它重复出现重复出现。3n动态规划算法与分治法类似，其基本思想动态规划算法与分治

3、法类似，其基本思想也是将待求解问题分解成若干个子问题。也是将待求解问题分解成若干个子问题。n但是经但是经分解得到的子问题往往不是互相分解得到的子问题往往不是互相独立的独立的。不同子问题的数目常常只有多。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子项式量级。在用分治法求解时，有些子问题被重复计算了许多次。问题被重复计算了许多次。4n 问题问题4-14-1：存在一个数字三角形，从顶到底有多：存在一个数字三角形，从顶到底有多条路径，条路径， 每一步可沿每一步可沿左斜线向下或垂直向下左斜线向下或垂直向下。路径。路径所经过的数字之和称为路径得分，要求求出最小路所经过的数字之和称为路径得分

4、，要求求出最小路径得分。径得分。n状态表示状态表示1-1 1-1 用一元组用一元组D D（X X）描述问题，）描述问题，D D（X X）表）表示从顶到达第示从顶到达第X X层的得分。但是一元组层的得分。但是一元组D D（X X）描述的子问题不能满足最优子）描述的子问题不能满足最优子结构性质，因为结构性质，因为D D（X X）的最优解可能）的最优解可能不包含子问题不包含子问题D D（X-IX-I）的最优解。这）的最优解。这样，动态规划方法是无法在状态表示样，动态规划方法是无法在状态表示1-11-1上应用。上应用。 动态规划对状态表示的要求动态规划对状态表示的要求 5n状态表示状态表示 1-2 1

5、-2 用二元组用二元组D D（X X，Y Y）描述问题，）描述问题，D D（X X，Y Y）表示到达第）表示到达第X X层第层第Y Y个位置时的得分，那么个位置时的得分，那么 D D（X X，Y Y）的最优解包）的最优解包含了子问题含了子问题D D（X+1X+1，Y Y）或）或D D（X+1X+1，Y-1Y-1）的最优解，）的最优解，状态转移方程为状态转移方程为 : :D D（X X，Y Y）= minD(X+1,Y),D(X+1,Y-1)+AX,Y= minD(X+1,Y),D(X+1,Y-1)+AX,Y D D（4 4，* *）= A4,= A4,* * 6D(i,j)1234567816

6、7256683634553438123812D(X，Y)= min D(X+1，Y),D(X+1,Y-1) + AX，Y 7声明部分；声明部分；输入输入a数组数组,M行行N列；列；/下标从下标从1开始开始for (j = 1; j =1; i-) /自底向上自底向上DP for (j =M-i+1,n=1; n=2*i; j+,n+) Dij=min(Di+1j,Di+1,j-1)+aij; coutmin(D1); /输出第一行最小值输出第一行最小值8D(i,j)123456781112343436566649136897D(X，Y)= min D(X-1，Y),D(X-1,Y+1) + A

7、X，Y 9动态规划设计一般要经历以下几个步骤：动态规划设计一般要经历以下几个步骤：1 1、划分、划分阶段阶段：按照问题的时间或空间特征，把问题：按照问题的时间或空间特征，把问题分为若干个阶段。分为若干个阶段。2 2、确定、确定状态状态：将问题发展到各个阶段时所处的各种：将问题发展到各个阶段时所处的各种客观情况用不同的状态表示出来。客观情况用不同的状态表示出来。3 3、确定决策并写出、确定决策并写出状态转移方程状态转移方程：因为决策和状态：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态，所以如果确定的状态和决策

8、来导出本阶段的状态，所以如果确定了决策，状态转移方程也就可以写出。了决策，状态转移方程也就可以写出。4 4、寻找、寻找边界条件边界条件：给出的状态转移方程是一个递推：给出的状态转移方程是一个递推式，需要一个式，需要一个递推的终止条件或边界条件递推的终止条件或边界条件。5 5、程序设计实现：动态规划的主要难点在于理论上、程序设计实现：动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。的设计，一旦设计完成，实现部分就会非常简单。101 1、阶段：把问题分成几个相互联系的有顺序的几、阶段：把问题分成几个相互联系的有顺序的几个个环节环节，这些环节即称为阶段。，这些环节即称为阶段。

9、2 2、状态：某一阶段的出发、状态：某一阶段的出发位置位置称为状态。称为状态。3 3、决策：从某阶段的一个状态演变到下一个阶段、决策：从某阶段的一个状态演变到下一个阶段某状态的某状态的选择选择。4 4、状态转移方程：前一阶段的终点就是后一阶段、状态转移方程：前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导出了后一阶段的状的起点，前一阶段的决策选择导出了后一阶段的状态，这种关系描述了由态，这种关系描述了由k k阶段到阶段到k+1k+1阶段状态的演变阶段状态的演变规律，称为状态转移方程。规律，称为状态转移方程。11n动态规划与一般搜索技术最大不同的地方就是动态规划与一般搜索技术最大不同的地方

10、就是记录了已求解过的问题的结果。记录了已求解过的问题的结果。n子问题的记录：子问题的记录：q最重要、最为复杂最重要、最为复杂q状态表示状态表示q用一个数、一组数或一个向量来实现状态表示用一个数、一组数或一个向量来实现状态表示n子问题结果的记录子问题结果的记录12n找出最优解的性质，并刻划其结构特征。找出最优解的性质，并刻划其结构特征。n递归地定义最优值递归地定义最优值。n以以自底向上自底向上的方式计算出最优值。的方式计算出最优值。n根据计算最优值时得到的信息，构造最优根据计算最优值时得到的信息，构造最优解。解。在动态规划中，可将一个问题的解决方案视为一在动态规划中，可将一个问题的解决方案视为一

11、系列决策的结果。不同的是，在贪婪算法中，每系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，采用一次贪婪准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。是否包含一个最优子序列。13动态规划设计的一般模式：动态规划设计的一般模式：for k=阶段最小值阶段最小值 to 阶段最大值阶段最大值 do /顺推每一个阶段顺推每一个阶段 for i=状态最小值状态最小值 to 状态最大值状态最大值 do /枚举阶段枚举阶段k的每一个状态的每一个状态 for j=决策最小值决策最小值

12、to 决策最大值决策最大值 do /枚举阶段枚举阶段k中状态中状态i可选择的每一种决策可选择的每一种决策fik=min(max)fik-1+aik-1,jk-1|ik-1通过决策通过决策jk-1可达可达ik14某个问题的最优解包含着其子问题的最优解某个问题的最优解包含着其子问题的最优解。这种性。这种性质称为质称为最优子结构性质最优子结构性质。例如图中，若路线例如图中，若路线I和和J是是A到到C的最的最优路径，则根据最优化原理，路线优路径，则根据最优化原理，路线J必是从必是从B到到C的最优路线。的最优路线。用反证法证明：假设有另一路径用反证法证明：假设有另一路径J是是B到到C的最优路径，则的最优

13、路径，则A到到C的的路线取路线取I和和J比比I和和J更优，矛盾。从更优，矛盾。从而证明而证明J必是必是B到到C的最优路径。的最优路径。最优子结构是问题能用动态规划算最优子结构是问题能用动态规划算法求解的前提。法求解的前提。15递归算法求解问题时，每次产生的子问题并不递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这总是新问题，有些子问题被反复计算多次。这种性质称为种性质称为子问题的重叠性质子问题的重叠性质。动态规划算法对每一个子问题只解一次，而后动态规划算法对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问将其解保存在一个表格中，当再次需要解此

14、子问题时，只是简单地用常数时间查看一下结果。题时，只是简单地用常数时间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。获得较高的解题效率。16备忘录方法的控制结构与直接递归方法的控制备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法结构相同，区别在于备忘录方法为每个解过的子为每个解过的子问题建立了备忘录问题建立了备忘录以备需要时查看，避免了相同以备需要时查看，避免了相同子问题的重复求解。子问题的重复求解。步骤：步骤：

15、为每个问题建立一个记录项，初值设为一个特为每个问题建立一个记录项，初值设为一个特殊值（表未求解）殊值（表未求解） 每个待求解子问题，首先查记录项，有解答则每个待求解子问题，首先查记录项，有解答则直接选取，否则求解该子问题。直接选取，否则求解该子问题。17问题描述问题描述给定给定n种物品和一背包。物品种物品和一背包。物品i的重的重量是量是wi，其价值为，其价值为vi，背包的容量为，背包的容量为C。问。问应如何选择装入背包的物品，使得装入背包应如何选择装入背包的物品，使得装入背包中物品的总价值最大中物品的总价值最大? 0-1背包问题是一个特殊的整数规划问题。背包问题是一个特殊的整数规划问题。nii

16、ixv1maxnixCxwiniii1,1 , 01181、减小规模、减小规模m(i，j)是背包容量为是背包容量为j，可选择物品为，可选择物品为i，i+1，n时时0-1背包问题的最优值。背包问题的最优值。m(i+1，j)可选择物品为可选择物品为i+1，n时时0-1背包问背包问题的最优值。题的最优值。m(n，j)可选择物品为可选择物品为n时时0-1背包问题的最优值。背包问题的最优值。规模已经为规模已经为1nnnwjwjvjnm00),(192、推导递归式，判断第、推导递归式，判断第i件？件？1）不放，背包当前产生价值仍为）不放，背包当前产生价值仍为m(i+1，j)；2）放入，调整背包容量）放入，

17、调整背包容量j-wi，背包当前产，背包当前产生价值为生价值为 m(i+1,j-wi)+vi20m(i，j)是背包容量为是背包容量为j，可选择物品为，可选择物品为i，i+1，n时时0-1背包问题的最优值。背包问题的最优值。由由0-1背包问题的最优子结构性质，可以建立背包问题的最优子结构性质，可以建立计算计算m(i，j)的递归式如下的递归式如下:iiiiwjwjjimvwjimjimjim0), 1(), 1(), 1(max),(nnnwjwjvjnm00),( void KnapSack(int v,int w,int c,int n,int m11)int jMax=min(wn,c);fo

18、r (j=0;jjMax;j+) /当当 0=jwn时时, m(n,j)=0 mnj=0;for (j=wn;j=wn时时, m(n,j)=vnmnj=vn;for (i=n-1;i=1;i-) /DP int jMax=min(wi,c); for (j=0;jjMax;j+) /m(i,j)=m(i+1,j) 当当0=jwi mij=mi+1j; for (j=wi;j=wn mij=max(mi+1j,mi+1j-wi+vi);cout2n时，算法需要时，算法需要(n2n)计算时间。计算时间。 m(i,j)值值0 1 2 3 4 5 6 7 8 9 1012345N=5，c=10，w=2

19、，2，6，5，4,v=6,3,5,4,6m(i，j)是背包是背包容量为容量为j，可选，可选择物品为择物品为i，i+1，n时时0-1背包问题的背包问题的最优值最优值24用倒推法来求出每种物品是否选中。选中用倒推法来求出每种物品是否选中。选中1，2，5三件物三件物品，最高价值品，最高价值15，总重，总重8。void traceback(int m11,int w,int c,int n,int x)for(i=1;i0 ? 1:0);N=5，c=10，w=2，2，6，5，4,v=6,3,5,4,6251、减小规模、减小规模m(i，j)是背包容量为是背包容量为j，可选择物品为，可选择物品为1,2,3

20、.i时时0-1背包问题的最优值。背包问题的最优值。m(i+1，j)可选择物品为可选择物品为1,2,3.i ,i+1时时0-1背包问背包问题的最优值。题的最优值。m(1，j)可选择物品为可选择物品为1时时0-1背包问题的最优值。背包问题的最优值。规模已经为规模已经为1111(1, )00jwvmjjw262、推导递归式，判断是否放入第、推导递归式，判断是否放入第i件？件？1）不放，背包当前产生价值仍为）不放，背包当前产生价值仍为m(i-1，j)；2）放入，调整背包容量）放入，调整背包容量j-wi，背包当前产生，背包当前产生价值为价值为 m(i-1,j-wi)+Vimax (1, ),(1,)(

21、, )0(1, )iiiijwm ij m ijwvm i jjwm ij111(1, )00jwvmjjw27N=5，c=10，w=2，2，6，5，4, v=6,3,5,4,6m(i,j)01234567891010066666666620066999999930066999911111440066999101113145006699121215151528某工厂预计明年有某工厂预计明年有A,B,C,D四个新四个新建项目，每个项目的投资额建项目，每个项目的投资额 wk及其及其投资后的收益投资后的收益 vk如下表所示。投资如下表所示。投资总额为总额为30万元，问如何选择项目才万元，问如何选择项

22、目才能使总收益最大。能使总收益最大。n上述问题的静态规划模型如下：上述问题的静态规划模型如下：项目项目wkvkA1512B108C129D85 项入选项入选项未入选项未入选 1 030)(maxkkxxwxvxfkkkkkkk291、描述该问题的最优解、描述该问题的最优解 若若x1 x2. xn是使总收益最大的最优解是使总收益最大的最优解(xi 0,1)，此时总投，此时总投资额为资额为C，投资项目的选择范围为，投资项目的选择范围为1n，我们将这个最优解记为，我们将这个最优解记为m1c; 则则x2 x3. xn也必定是在总投资额为也必定是在总投资额为c-w1x1 (当当x1=0时为时为c，x1=1时为时为c-w1)，投资项目的选择范围为，投资项目的选择范围为2n时的子问题的最优解，时的子问题的最优解，我们将其记为我们将其记为m2c-w1x1; 此时我们需要证明这一结论，用反证法即可。此时我们需要证明这一结论，用反证法即可。证明：证明： 假设假设x2 x3. xn不是当前状态的最优解，则必定存在一个