动态规划之01背包讲解

《动态规划之01背包讲解》由会员分享，可在线阅读，更多相关《动态规划之01背包讲解（31页珍藏版）》请在金锄头文库上搜索。

1、1 学习要点: 理解动态规划算法的概念。 掌握动态规划算法的基本要素 （1）最优子结构性质 （2）重叠子问题性质 掌握设计动态规划算法的步骤。 (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解。 动态规划动态规划(DP)(DP) Dynamic ProgrammingDynamic Programming 2 n动态规划法的定义：在求解问题中，对于 每一步决策，列出各种可能的局部解，再 依据某种判定条件，舍弃那些肯定不能得 到最优解的局部解，在每一步都经过筛选 ，以每一步都是最优解来保证全局

2、是最优 解。 4.14.1算法总体思想算法总体思想 n动态规划通常应用于最优化问题，即做出 一组选择以达到一个最优解。关键是存储 子问题的每一个解，以备它重复出现。 3 n动态规划算法与分治法类似，其基本思想 也是将待求解问题分解成若干个子问题。 4.14.1算法总体思想算法总体思想 n但是经分解得到的子问题往往不是互相 独立的。不同子问题的数目常常只有多 项式量级。在用分治法求解时，有些子 问题被重复计算了许多次。 4 n问题4-1：存在一个数字三角形，从顶到底有多 条路径， 每一步可沿左斜线向下或垂直向下。路径 所经过的数字之和称为路径得分，要求求出最小路径 得分。 n状态表示1-1 用一

3、元组D（X）描述问题，D（X）表 示从顶到达第X层的得分。但是一元组 D（X）描述的子问题不能满足最优子 结构性质，因为D（X）的最优解可能 不包含子问题D（X-I）的最优解。这 样，动态规划方法是无法在状态表示1 -1上应用。 动态规划对状态表示的要求 5 n状态表示 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,Y D（4，*）= A4,* 6 D(i,j)12345678

4、167 25668 3634553 438123812 D(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=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,

5、j)值 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 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 4.3 典型问题典型问题0-10-1背包问题背包问题 用倒推法来求出每种物品是否选中。选中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,6 25 4.3 0-1

6、4.3 0-1背包问题背包问题- -改变改变m(i,j)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 4.3 典型问题典型问题0-10-1背包问题背包问题 2、推导递归式，判断是否放入第i件？ 1）不放，背包当前产生价值仍为m(i-1，j)； 2）放入，调整背包容量j-wi，背包当前产生 价值为 m(i-1,j-wi)+Vi 27 4.3 4.3 典型问题典型

7、问题0-10-1背包问题背包问题 N=5，c=10，w=2，2，6，5，4, v=6,3,5,4,6 m(i,j ) 012345678910 100666666666 200669999999 300669999111114 4006699910111314 50066991212151515 28 思考与练习思考与练习项目选择问题项目选择问题 某工厂预计明年有A,B,C,D四个新 建项目，每个项目的投资额 wk及其 投资后的收益 vk如下表所示。投资 总额为30万元，问如何选择项目才 能使总收益最大。 n上述问题的静态规划模型如下： 29 分析分析项目选择问题项目选择问题 1、描述该问题的

8、最优解 若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不是当前状态的最优解，则必定存在一个解z2 z3 zn为最优解，这样对于整个问题的最优解就应该是x1 z2 z3 Zn。这显然与x1 x2 xn为最优解相矛盾，故假设不成立， 得证。 2、递归定义最优解 若我们

9、把投资总额为j，投资项目的选择范围为in时 的问题的最优解定义为mij； 显然，按照第一步的模式，m1c的子问题的最优解 为m2c-w1x1，那么mij的子问题的最优解就应该为 mi+1j-wixi； 于是我们可以把这个问题递归定义为： mij=maxmi+1j,mi+1j-wi+vi（这两项是由xi的两种 取值不同而来的） 再根据j的取值范围我们便可以得到这个问题的递归 式： 边界条件为 ： 31 3、以自底向上的方式计算出最优值 void KnapSack(int v,int w,int c,int n,int m11) int jMax=min(wn-1,c); for (j=0;j=jMax;j+) mnj=0; for (j=wn;j1;i-) int jMax=min(wi-1,c); for (j=0;j=jMax;j+) mij=mi+1j; for (j=wi;j=w1) m1c=max(m1c,m2c-w1+v1);