动态规划之01背包

1,学习要点:理解动态规划算法的概念。掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质掌握设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。,动态规划(DP)DynamicProgramming,2,动态规划法的定义：在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。,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）=minD(X+1,Y),D(X+1,Y-1)+AX,YD（4，*）=A4,*,6,D(X，Y)=minD(X+1，Y),D(X+1,Y-1)+AX，Y,7,声明部分；输入a数组,M行N列；/下标从1开始for(j=1;j=1;i-)/自底向上DPfor(j=M-i+1,n=1;n=2*i;j+,n+)Dij=min(Di+1j,Di+1,j-1)+aij;cout=1;i-)/DPintjMax=min(wi,c);for(j=0;j=wnmij=max(mi+1j,mi+1j-wi+vi);cout2n时，算法需要(n2n)计算时间。,N=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背包问题的最优值,24,4.3典型问题0-1背包问题,用倒推法来求出每种物品是否选中。选中1，2，5三件物品，最高价值15，总重8。,voidtraceback(intm11,intw,intc,intn,intx)for(i=1;i0?1:0);,N=5，c=10，w=2，2，6，5，4,v=6,3,5,4,6,25,4.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背包问题的最优值。规模已经为1,26,4.3典型问题0-1背包问题,2、推导递归式，判断是否放入第i件？1）不放，背包当前产生价值仍为m(i-1，j)；2）放入，调整背包容量j-wi，背包当前产生价值为m(i-1,j-wi)+Vi,27,4.3典型问题0-1背包问题,N=5，c=10，w=2，2，6，5，4,v=6,3,5,4,6,28,思考与练习项目选择问题,某工厂预计明年有A,B,C,D四个新建项目，每个项目的投资额wk及其投资后的收益vk如下表所示。投资总额为30万元，问如何选择项目才能使总收益最大。上述问题的静态规划模型如下：,29,分析项目选择问题,1、描述该问题的最优解若x1x2.xn是使总收益最大的最优解(xi0,1)，此时总投资额为C，投资项目的选择范围为1n，我们将这个最优解记为m1c;则x2x3.xn也必定是在总投资额为c-w1x1(当x1=0时为c，x1=1时为c-w1)，投资项目的选择范围为2n时的子问题的最优解，我们将其记为m2c-w1x1;此时我们需要证明这一结论，用反证法即可。证明：假设x2x3.xn不是当前状态的最优解，则必定存在一个解z2z3.zn为最优解，这样对于整个问题的最优解就应该是x1z2z3.Zn。这显然与x1x2.xn为最优解相矛盾，故假设不成立，得证。,2、递归定义最优解若我们把投资总额为j，投资项目的选择范围为in时的问题的最优解定义为mij；显然，按照第一步的模式，m1c的子问题的最优解为m2c-w1x1，那么mij的子问题的最优解就应该为mi+1j-wixi；于是我们可以把这个问题递归定义为：mij=maxmi+1j,mi+1j-wi+vi（这两项是由xi的两种取值不同而来的）再根据j的取值范围我们便可以得到这个问题的递归式：,边界条件为：,31,3、以自底向上的方式计算出最优值voidKnapSack(intv,