动态规划之01背包

1学习要点:理解动态规划算法的概念。掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质掌握设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。动态规划(DP)DynamicProgramming2动态规划法的定义：在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。4.1算法总体思想动态规划通常应用于最优化问题，即做出一组选择以达到一个最优解。关键是存储子问题的每一个解，以备它重复出现。3动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。4.1算法总体思想但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。4[问题4-1]：存在一个数字三角形，从顶到底有多条路径，每一步可沿左斜线向下或垂直向下。路径所经过的数字之和称为路径得分，要求求出最小路径得分。状态表示1-1用一元组D（X）描述问题，D（X）表示从顶到达第X层的得分。但是一元组D（X）描述的子问题不能满足最优子结构性质，因为D（X）的最优解可能不包含子问题D（X-I）的最优解。这样，动态规划方法是无法在状态表示1-1上应用。动态规划对状态表示的要求5状态表示1-2用二元组D（X，Y）描述问题，D（X，Y）表示到达第X层第Y个位置时的得分，那么D（X，Y）的最优解包含了子问题D（X+1，Y）或D（X+1，Y-1）的最优解，状态转移方程为:D（X，Y）=min{D(X+1,Y),D(X+1,Y-1)}+A[X,Y]D（4，*）=A[4,*]6D(i,j)12345678167256683634553438123812D(X，Y)=min{D(X+1，Y),D(X+1,Y-1)}+A[X，Y]7声明部分；输入a数组,M行N列；//下标从1开始for(j=1;j=N;j++)//O(N)D[M][j]=a[M][j];for(i=M-1;i=1;i--)//自底向上DP{for(j=M-i+1,n=1;n=2*i;j++,n++)D[i][j]=min(D[i+1][j],D[i+1,j-1])+a[i][j];}coutmin(D[1]);//输出第一行最小值}8D(i,j)123456781112343436566649136897D(X，Y)=min{D(X-1，Y),D(X-1,Y+1)}+A[X，Y]94.1算法总体思想动态规划设计一般要经历以下几个步骤：1、划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。2、确定状态：将问题发展到各个阶段时所处的各种客观情况用不同的状态表示出来。3、确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态，所以如果确定了决策，状态转移方程也就可以写出。4、寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。5、程序设计实现：动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。104.1算法总体思想1、阶段：把问题分成几个相互联系的有顺序的几个环节，这些环节即称为阶段。2、状态：某一阶段的出发位置称为状态。3、决策：从某阶段的一个状态演变到下一个阶段某状态的选择。4、状态转移方程：前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导出了后一阶段的状态，这种关系描述了由k阶段到k+1阶段状态的演变规律，称为状态转移方程。114.1算法总体思想动态规划与一般搜索技术最大不同的地方就是记录了已求解过的问题的结果。子问题的记录：最重要、最为复杂状态表示用一个数、一组数或一个向量来实现状态表示子问题结果的记录12动态规划基本步骤找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。134.1算法总体思想动态规划设计的一般模式：fork=阶段最小值to阶段最大值do//顺推每一个阶段fori=状态最小值to状态最大值do//枚举阶段k的每一个状态forj=决策最小值to决策最大值do//枚举阶段k中状态i可选择的每一种决策f[ik]=min(max){f[ik-1]+a[ik-1,,jk-1]|ik-1通过决策jk-1可达ik}144.2动态规划算法的基本要素一、最优子结构•某个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。例如图中，若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最优路线。用反证法证明：假设有另一路径J‘是B到C的最优路径，则A到C的路线取I和J’比I和J更优，矛盾。从而证明J‘必是B到C的最优路径。最优子结构是问题能用动态规划算法求解的前提。154.2动态规划算法的基本要素二、重叠子问题•递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。•动态规划算法对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。•通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。164.2动态规划算法的基本要素三、备忘录方法•备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。•步骤：为每个问题建立一个记录项，初值设为一个特殊值（表未求解）每个待求解子问题，首先查记录项，有解答则直接选取，否则求解该子问题。174.3典型问题——0-1背包问题[问题描述]给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?0-1背包问题是一个特殊的整数规划问题。niiixv1maxnixCxwiniii1},1,0{1184.3典型问题——0-1背包问题1、减小规模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背包问题的最优值。规模已经为1nnnwjwjvjnm00),(194.3典型问题——0-1背包问题2、推导递归式，判断第i件？1）不放，背包当前产生价值仍为m(i+1，j)；2）放入，调整背包容量j-wi，背包当前产生价值为m(i+1,j-wi)+vi204.3典型问题——0-1背包问题m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下:iiiiwjwjjimvwjimjimjim0),1(}),1(),,1(max{),(nnnwjwjvjnm00),(voidKnapSack(intv[],intw[],intc,intn,intm[][11]){intjMax=min(w[n],c);for(j=0;jjMax;j++)//当0=jw[n]时,m(n,j)=0m[n][j]=0;for(j=w[n];j=c;j++)//当j=w[n]时,m(n,j)=v[n]m[n][j]=v[n];for(i=n-1;i=1;i--)//DP{intjMax=min(w[i],c);for(j=0;jjMax;j++)//m(i,j)=m(i+1,j)当0=jw[i]m[i][j]=m[i+1][j];for(j=w[i];j=c;j++)//m(n,j)=v[n]当j=w[n]m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}coutm[1][c];//在C容量可获的最大价值}224.3典型问题——0-1背包问题n=5，c=10，w={2，2，6，5，4},v={6,3,5,4,6}m(i,j)012345678910115200336699910113000066666101140000666661010500006666666234.3典型问题——0-1背包问题算法复杂度分析：从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c2n时，算法需要Ω(n2n)计算时间。m(i,j)值01234567891012345N=5，c=10，w={2，2，6，5，4},v={6,3,5,4,6}m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值244.3典型问题——0-1背包问题用倒推法来求出每种物品是否选中。选中1，2，5三件物品，最高价值15，总重8。voidtraceback(intm[][11],intw[],intc,intn,intx[]){for(i=1;in;i++)if(m[i][c]==m[i+1][c])x[i]=0;else{x[i]=1;c=c-w[i];}x[n]=(m[n][c]0?1:0);}N=5，c=10，w={2，2，6，5，4},v={6,3,5,4,6}254.30-1背包问题-改变m(i,j)含义1、减小规模m(i，j)是背包容量为j，可选择物品为1,2,3...i时0-1背包问题的最优值。m(i+1，j)可选择物品为1,2,3...i,i+1时0-1背包问题的最优值。…m(1，j)可选择物品为1时0-1背包问题的最优值。规模已经为1111(1,)00jwvmjjw264.3典型问题——0-1背包问题2、推导递归式，判断是否放入第i件？1）不放，背包当前产生价值仍为m(i-1，j)；2）放入，调整背包容量j-wi，背包当前产生价值为m(i-1,j-wi)+Vimax{(1,),(1,)}(,)0(1,)iiiijwmijmijwvmijjwmij111(1,)00jwvmjjw274.3典型问题——0-1背包问题N=5，c=10，w={2，2，6，5，4},v={6,3,5,4,6}m(i,j)01234567891010066666666620066999999930066999911111440066999101113145006699121215151528思考与练习——项目选择问题某工厂预计明年有A,B,C,D四个新建项目，每个项目的投资额wk及其投资后的收益vk如下表所示。投资总额为30万元，问如何选择项目才能使总收益最大。上述问题的静态规划模型如下：项入选项未入选1030)(maxkkxxwxvxfkkkkkkk29分析——项目选择问题1、描述该问题的最优解若x1x2…..xn是使总收益最大的最优解(xi∈{0,1})，此时总投资额为C，投资项目的选择范围为1~n，我们将这个最优解记为m[1][c];则x2x3…..xn也必定是在总投资额为c-w1x1(当x1=0时为c，x1=1时为c-w1)，投资项目的选择范围为2~n时的子问题的最优解，我们将其记为m[2][c-w1x1];此时我们需要证明这一结论，用反证法即可。证明：假设x2x3…..xn不是当前状态的最优解，则必定存在一个解z2z3…..zn为最优解，这样