动态规划基础(2)

1、动态规划的基础动态规划的基础(2)背包，树形背包，树形清华大学 莫涛资源分配类动态规划资源分配类动态规划l问题描述有一个基本要素：资源，有时这种资源可能是金问题描述有一个基本要素：资源，有时这种资源可能是金钱、空间或者时间，问题就是要对这些资源如何分配，一钱、空间或者时间，问题就是要对这些资源如何分配，一种基本的想法是将资源应用于前种基本的想法是将资源应用于前i个阶段，然后考虑第个阶段，然后考虑第i个个阶段和前阶段和前i-1个阶段之间的关系。个阶段之间的关系。l设前设前i个点的消耗个点的消耗j的资源得到的最优值，研究前的资源得到的最优值，研究前i-1个点消个点消耗的资源的最优值，利用第耗的资源

2、的最优值，利用第i个点决策转移，如下图。个点决策转移，如下图。l状态转移方程一般可写成状态转移方程一般可写成: f fi i(j) = min fi-1i-1 ( k) + ui (j,k) 经典的背包问题（经典的背包问题（01背包）背包）l有有N件物品件物品;l第第i件物品件物品Wi公斤公斤;l第第i件物品价值件物品价值Ci元元;l现有一辆载重现有一辆载重M公斤的卡车公斤的卡车;l问选取装载哪些物品，使得卡车运送的总问选取装载哪些物品，使得卡车运送的总价值最大？价值最大？搜索法搜索法l对于每种物品，要么装上卡车，要么不装，因此，对于每种物品，要么装上卡车，要么不装，因此，N种种物品的装箱方案

3、共有物品的装箱方案共有2N种。种。l按每种物品进行搜索，方法如下：按每种物品进行搜索，方法如下：l对第对第i种物品进行搜索种物品进行搜索l如果所有的物品都搜索完，则更新最优解如果所有的物品都搜索完，则更新最优解l如果当前的估计达不到最优解，则回溯如果当前的估计达不到最优解，则回溯l如果第如果第i种物品能放，则放，并标记，否则选下一个种物品能放，则放，并标记，否则选下一个物品物品l清除标记清除标记l回溯回溯动态规划动态规划l可以按每个物品进行规划，同样每种物品有选和不选两种选择l设F(i,j)表示前i件物品载重为j的最大效益，则有l1=i=N, 0=j=wi then /背包容量够大 fi,j:

4、=max(fi-1,j-wi+ci,fi-1,j)else /背包容量不足 fi,j:=fi-1,j;end;满背包问题（满背包问题（01背包）背包）l有有N件物品件物品;l第第i件物品件物品Wi公斤公斤;l第第i件物品价值件物品价值Ci元元;l现有一辆载重现有一辆载重M公斤的卡车公斤的卡车;l问选取装载哪些物品，使得卡车开车正好问选取装载哪些物品，使得卡车开车正好装满时，运送的总价值最大？装满时，运送的总价值最大？若无法装满卡车，则输出无解。若无法装满卡车，则输出无解。动态规划动态规划l设F(i,j)表示前i件物品背包为j的最大效益，则有l1=i=N, 0=j0)= -lF(N,M)即答案l

5、显然时间复杂度为O(NM)种物品不装载第种物品装载第ijiFiiCiwjiFMaxjiF), 1(,), 1(),(带条件的背包问题（带条件的背包问题（1）l有有N件物品件物品;l第第i件物品件物品Wi公斤公斤;l第第i件物品价值件物品价值Ci元元;l第第i件物品可能带件物品可能带02个附件；个附件；l若装载附件，必须装载主件，反之没有约束；若装载附件，必须装载主件，反之没有约束；l现有一辆载重现有一辆载重M公斤的卡车公斤的卡车;l问选取装载哪些物品，使得卡车运送的总价值最问选取装载哪些物品，使得卡车运送的总价值最大？大？分析分析l假设只有主件的情况假设只有主件的情况 ，显然与经典背包问题完，

6、显然与经典背包问题完全相同！全相同！l现在每个物品有附件，我们可以分成现在每个物品有附件，我们可以分成4种方案种方案l仅装载主件仅装载主件l装载主件装载主件+第第1个附件个附件l装载主件装载主件+第第2个附件个附件l装载主件装载主件+2个附件个附件l由于上述由于上述4种并列，这是几种不同的决策同时规种并列，这是几种不同的决策同时规划即可划即可动态规划动态规划l设设F(i,j)表示前表示前i件物品背包为件物品背包为j的最优解，则有，的最优解，则有，l1=i=N, 0=j=Ml时间复杂度时间复杂度O(NM)件附件选主件和，件附件选主件和第，件附件选主件和第，只选主件件物品不选第2/21)2-1w-

7、, 1(2/2)2-, 1(1/1)1w-, 1(), 1(i), 1(),(iciciciwiiwjiFiciciwiwjiFiciciiwjiFiciwjiFjiFMaxjiF多层背包问题多层背包问题l有有N件物品件物品;l第第i件物品件物品Wi公斤公斤;l第第i件物品价值件物品价值Ci元元;l现有一辆载重现有一辆载重M公斤的卡车公斤的卡车;l第第i件物品限制最多只能取件物品限制最多只能取Xi个；个；l问选取装载哪些物品，使得卡车运送的总价值问选取装载哪些物品，使得卡车运送的总价值最大？最大？分析分析l我们可以类似我们可以类似01背包问题，将第背包问题，将第i种物品拆分成种物品拆分成xi个

8、，这样每个物品只有个，这样每个物品只有1件了件了,如下图如下图:l然后对所有的物品采用动态规划即可。然后对所有的物品采用动态规划即可。lF(i,j)=max f(i-1,j-k*wi) + k*ci l0=k*wi=j完全背包问题完全背包问题l有有N件物品件物品;l第第i件物品件物品Wi公斤公斤;l第第i件物品价值件物品价值Ci元元;l现有一辆载重现有一辆载重M公斤的卡车公斤的卡车;l每次可以选取某种物品的任意多件装载；每次可以选取某种物品的任意多件装载；l问选取装载哪些物品，使得卡车运送的总价值问选取装载哪些物品，使得卡车运送的总价值最大？最大？分析分析l类似多层背包问题将每个物品展开成类似

9、多层背包问题将每个物品展开成Xi =m/wi个，然个，然后对所有的物品采用动态规划即可。后对所有的物品采用动态规划即可。l若两件物品若两件物品i、j满足满足ci=wj,则将物品则将物品i去去掉掉,不用考虑。这个优化的正确性显然：任何情况下都可不用考虑。这个优化的正确性显然：任何情况下都可将价值小费用高的将价值小费用高的j换成物美价廉的换成物美价廉的i,得到至少不会更差得到至少不会更差的方案。的方案。l由于每种物品有选和不选两种情况，可以将每种物品的由于每种物品有选和不选两种情况，可以将每种物品的2k个当成一个整体考虑。这样对于某种物品要选取多个个当成一个整体考虑。这样对于某种物品要选取多个，都

10、可以由若干个，都可以由若干个2k个物品进行组合个物品进行组合 (即即2进制数进制数)。例如。例如第第i种物品要选种物品要选10个，则个，则10=23+21 。l这样第这样第i种物品的个数为种物品的个数为k=2 (m/wi)物品，是一个很大物品，是一个很大的改进。的改进。l进一步进一步, 在计算在计算k时时, K =2 (j/wi), j为当前背包剩余空间为当前背包剩余空间。进一步进一步for i:=1 to n do / 动态规划，递推求动态规划，递推求ffor j:=m downto 1 dobeginif j=wi then /背包容量够大背包容量够大 fi,j:=max(fi-1,j-w

11、i+ci,fi-1,j)else /背包容量不足背包容量不足 fi,j:=fi-1,j;end; 在这里为了使得每个物品只取在这里为了使得每个物品只取1个或不取个或不取,采用了每次取采用了每次取j都都是与是与i-1进行比较，实际上保存了每进行比较，实际上保存了每1步取不同步取不同j的值的值改进程序改进程序l事实上，我们只关心剩余背包的最大值，也就是事实上，我们只关心剩余背包的最大值，也就是仅仅关心仅仅关心f(j),因此，在对因此，在对f(j)更新时，只要背包容更新时，只要背包容量可以，那么可以反复更新。程序如下：量可以，那么可以反复更新。程序如下：for i:=1 to n do / 动态规划

12、，递推求动态规划，递推求ffor j:=0 to m dobeginif j=wi then /背包容量够大背包容量够大 fj:=max(fj-wi+ci,fj)end;思考题思考题1：机器分配：机器分配 lM M台设备，分给台设备，分给N N个公司。个公司。l若公司若公司i i获得获得j j台设备，则能产生台设备，则能产生AijAij效益效益l问如何分配设备使得总效益最大？问如何分配设备使得总效益最大？lM M =15=15，N=10N=10。分析分析l用机器数来做状态，数组f(i,j)表示前i个公司分配j台机器的最大盈利。则状态转移方程为:lf(i,j) =Maxfi-1，k + ai，j

13、-j (1=i=N,1=j=M,0=k=j )l初始值: f(0,0)=0l时间复杂度O(N*M2)思考题思考题2：硬币找零：硬币找零l给定给定N枚硬币枚硬币l给定给定T元钱元钱l用这用这N枚硬币找这枚硬币找这T元钱，使得剩下的钱最少元钱，使得剩下的钱最少。l剩下钱数最少的找零方案中的所需的最少硬币剩下钱数最少的找零方案中的所需的最少硬币数。数。lN=500,T=10000.分析分析l设设Fi表示需要找的钱数为表示需要找的钱数为i时所需要的最少钱时所需要的最少钱币数。显然有：币数。显然有：lFi=MinF i - Aj + 1 i T，1jNl初始值：初始值：F0=0。lAj表示其中表示其中

14、第第j种钱币的面值。种钱币的面值。l时间复杂度为时间复杂度为O(N*T)。思考题思考题3：系统可靠性：系统可靠性l一个系统由若干部件串联而成，只要有一个部件一个系统由若干部件串联而成，只要有一个部件故障，系统就不能正常运行，为提高系统的可靠故障，系统就不能正常运行，为提高系统的可靠性，每一部件都装有备用件，一旦原部件故障，性，每一部件都装有备用件，一旦原部件故障，备用件就自动进入系统。显然备用件越多，系统备用件就自动进入系统。显然备用件越多，系统可靠性越高，但费用也越大，那么在一定总费用可靠性越高，但费用也越大，那么在一定总费用限制下，系统的最高可靠性等于多少？限制下，系统的最高可靠性等于多少

15、？l给定一些系统备用件的单价给定一些系统备用件的单价CkCk，以及当用，以及当用MkMk个此个此备用件时部件的正常工作概率备用件时部件的正常工作概率PkPk（MkMk），总费用），总费用上限上限C C。求系统可能的最高可靠性。求系统可能的最高可靠性。 样例样例输入文件格式：输入文件格式：第一行：第一行：n Cn C第二行：第二行：C1 P1(0) P1(1) C1 P1(0) P1(1) P1(X1) P1(X1) （0=X1=C/Ck0=X1=C/Ck） 第第n n 行：行：Cn Pn(0) Pn(1) Cn Pn(0) Pn(1) Pn(Xn) Pn(Xn) （0=Xn=C/Cn0=Xn=

16、C/Cn）输入：输入：2 202 20 3 0.6 0.65 0.7 0.75 0.8 0.85 0.93 0.6 0.65 0.7 0.75 0.8 0.85 0.9 5 0.7 0.75 0.8 0.9 0.95 5 0.7 0.75 0.8 0.9 0.95输出：输出：0.6375=0.750.6375=0.75* *0.850.85分析分析l设设f(i,j)f(i,j)表示将表示将j j的资金用到前的资金用到前i i项备用件中去项备用件中去的最大可靠性，则有的最大可靠性，则有 F(i,j)=F(i,j)= maxF(i-1,j maxF(i-1,jk k* *Costi)Costi)*

17、 *Pi,kPi,kl 0=i=n, 0=j=C, 0=i=n, 0=j=C,0=0=k kj div Cost(j div Cost(i i) )l初始：初始： F(0,0)=1F(0,0)=1l目标：目标： F(n,C)F(n,C)l时间复杂度：时间复杂度：O(kO(k* *n n* *C)C)，这里，这里k k是常数因子，是常数因子，与数据相关与数据相关树形动态规划问题树形动态规划问题l基本模型都是一棵树或者森林，为了考虑方便，一般情况基本模型都是一棵树或者森林，为了考虑方便，一般情况下都将这个树或森林转化为二叉树，如下图，然后整个问下都将这个树或森林转化为二叉树，如下图，然后整个问题的

18、最优只会涉及到左右孩子的最优，然后考虑根结点的题的最优只会涉及到左右孩子的最优，然后考虑根结点的情况，这样化简了问题，最终很容易写出状态转移方程，情况，这样化简了问题，最终很容易写出状态转移方程，从而问题得到解决。从而问题得到解决。 l另外，并不是所有的问题一定要转化为二叉树来解决，要另外，并不是所有的问题一定要转化为二叉树来解决，要仔细思考的就是每个结点有些什么状态，这些结点的状态仔细思考的就是每个结点有些什么状态，这些结点的状态与父、子结点的状态有什么联系，也就是如何由子结点的与父、子结点的状态有什么联系，也就是如何由子结点的最优值推出父节点的最优值最优值推出父节点的最优值(即状态转移方程

19、即状态转移方程)。加分二叉树加分二叉树l给定一个中序遍历为给定一个中序遍历为1,2,3,n的二叉树的二叉树l每个结点有一个权值每个结点有一个权值l定义二叉树的加分规则为：定义二叉树的加分规则为：l左子树的加分左子树的加分 右子树的加分根的分数右子树的加分根的分数l若某个树缺少左子树或右子树，规定缺少的子树加若某个树缺少左子树或右子树，规定缺少的子树加分为分为1。l构造符合条件的二叉树构造符合条件的二叉树l该树加分最大该树加分最大l输出其前序遍历序列输出其前序遍历序列l样例样例l中序遍历为中序遍历为1,2,3,4,5的二叉树有很多，下图是的二叉树有很多，下图是其中的三棵，其中第三棵加分最大，为其

20、中的三棵，其中第三棵加分最大，为145.分析分析l性质：中序遍历是按性质：中序遍历是按“左左-根根-右右”方式进行遍历二叉树，方式进行遍历二叉树，因此二叉树左孩子遍历序列一定在根结点的左边，右孩子因此二叉树左孩子遍历序列一定在根结点的左边，右孩子遍历序列一定在根结点的右边！遍历序列一定在根结点的右边！l因此，假设二叉树的根结点为因此，假设二叉树的根结点为k，那么中序遍历为，那么中序遍历为1,2,n的遍历序列，左孩子序列为的遍历序列，左孩子序列为1,2,k-1，右孩子序列为，右孩子序列为k+1,k+2,n，如下图，如下图动态规划动态规划l设设f(i,j)中序遍历为中序遍历为i,i+1,j的二叉树

21、的最大加分，的二叉树的最大加分，则有：则有： f(i,j)=maxfi,k-1*fk+1,j +dkl显然显然 f(i,i)=dil答案为答案为f(1,n)l1=i=k=j=nl时间复杂度时间复杂度 O(n3)l要构造这个树，只需记录每次的决策值，令要构造这个树，只需记录每次的决策值，令b(i,j)=k，表示中序遍历为，表示中序遍历为i,i+1,j的二叉树的取最的二叉树的取最优决策时的根结点为优决策时的根结点为kl最后前序遍历这个树即可。最后前序遍历这个树即可。选课选课l给定给定M门课程，每门课程有一个学分门课程，每门课程有一个学分l要从要从M门课程中选择门课程中选择N门课程，使得学分总和门课

22、程，使得学分总和最大最大l其中选择课程必须满足以下条件：其中选择课程必须满足以下条件：l每门课程最多只有一门直接先修课每门课程最多只有一门直接先修课l要选择某门课程，必须先选修它的先修课要选择某门课程，必须先选修它的先修课lM,N=500分析分析l每门课程最多只有每门课程最多只有1门直接先修课，如果我们把门直接先修课，如果我们把课程看成结点，也就是说每个结点最多只一个前课程看成结点，也就是说每个结点最多只一个前驱结点。驱结点。l如果把前驱结点看成父结点，换句话说，每个结如果把前驱结点看成父结点，换句话说，每个结点只有一个父结点。显然具有这种结构的模型是点只有一个父结点。显然具有这种结构的模型是

23、树结构，要么是一棵树，要么是一个森林。树结构，要么是一棵树，要么是一个森林。l这样，问题就转化为在一个这样，问题就转化为在一个M个结点的森林中选个结点的森林中选取取N个结点，使得所选结点的权值之和最大。同个结点，使得所选结点的权值之和最大。同时满足每次选取时，若选儿子结点，必选根结点时满足每次选取时，若选儿子结点，必选根结点的条件。的条件。样例分析样例分析l如图如图1，为两棵树，我们可以虚拟一个结点，将，为两棵树，我们可以虚拟一个结点，将这些树连接起来，那么森林就转会为了这些树连接起来，那么森林就转会为了1棵树，棵树，选取结点时，从每个儿子出发进行选取。显然选选取结点时，从每个儿子出发进行选取

24、。显然选M=4时，选时，选3，2，7，6几门课程最优。几门课程最优。转化为二叉树转化为二叉树如果该问题仅仅只是一棵二叉树，我们对儿子的分配就仅如果该问题仅仅只是一棵二叉树，我们对儿子的分配就仅仅只需考虑左右孩子即可，问题就变得很简单了。因此我仅只需考虑左右孩子即可，问题就变得很简单了。因此我们试着将该问题转化为二叉树求解。们试着将该问题转化为二叉树求解。图图2就是对图就是对图1采用孩子兄弟表示法所得到的二叉树采用孩子兄弟表示法所得到的二叉树动态规划动态规划l仔细理解左右孩子的意义（如右图）：仔细理解左右孩子的意义（如右图）：左孩子：原根结点的孩子左孩子：原根结点的孩子右孩子：原根结点的兄弟右孩

25、子：原根结点的兄弟l也就是说，左孩子分配选课资源时，也就是说，左孩子分配选课资源时，根结点必须要选修，而与右孩子无关。根结点必须要选修，而与右孩子无关。l因此，我们设因此，我们设f(i,j)表示以表示以i为根结点的二叉树分配为根结点的二叉树分配j门课程的所获门课程的所获得的最大学分，则有，得的最大学分，则有，l0=kj n m; scoren+1 = 0; brothern+1 = 0; / 输入数据并转化为左儿子右兄弟表示法输入数据并转化为左儿子右兄弟表示法 for (int i=1; i a b; if (a = 0) a = n + 1; scorei = b; brotheri = c

26、hilda; childa = i; void dfs( int i, int j) if (visitedij) return; visitedij = 1; if (i=0 | j=0) return; dfs(brotheri, j); / 如果不选如果不选i，则转移到状态，则转移到状态(brotheri, j) fij = fbrotherij; for (int k=0; k fij) fij = fbrotherik + fchildij-k-1 + scorei; 软件安装软件安装（2010河南省选）河南省选）l有有N个软件，对于一个软件个软件，对于一个软件i，它要占用，它要占用

27、Wi的磁盘空间，的磁盘空间，它的价值为它的价值为Vi。我们希望从中选择一些软件安装到一台。我们希望从中选择一些软件安装到一台磁盘容量为磁盘容量为M计算机上，使得这些软件的价值尽可能大计算机上，使得这些软件的价值尽可能大（即（即Vi的和最大）。的和最大）。l软件之间存在依赖关系，即软件软件之间存在依赖关系，即软件i只有在安装了软件只有在安装了软件j（包括软件（包括软件j的直接或间接依赖）的情况下才能正确工作的直接或间接依赖）的情况下才能正确工作（软件（软件i依赖软件依赖软件j)。幸运的是，一个软件最多依赖另外。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发一个软件

28、。如果一个软件不能正常工作，那么它能够发挥的作用为挥的作用为0。l我们现在知道了软件之间的依赖关系：软件我们现在知道了软件之间的依赖关系：软件i依赖软件依赖软件Di。 一个软件只能被安装一次，如果一个软件没有依赖则一个软件只能被安装一次，如果一个软件没有依赖则Di=0，这时只要这个软件安装了，它就能正常工作。，这时只要这个软件安装了，它就能正常工作。l现在请你设计出一种方案，安装价值尽量大的软件。现在请你设计出一种方案，安装价值尽量大的软件。分析分析l由于软件存在先后约束关系，因此简单按软件先后顺序进行动由于软件存在先后约束关系，因此简单按软件先后顺序进行动态规划，会不符合无后效应原理，因此我

29、们需要在进行动态规态规划，会不符合无后效应原理，因此我们需要在进行动态规划前进行预处理。划前进行预处理。l若安装软件若安装软件i必须先安装必须先安装j,则从则从i向向j连一条有向弧，则软件的约束连一条有向弧，则软件的约束关系就构成了一个有向图。如下图：关系就构成了一个有向图。如下图：l可以看出如果有可以看出如果有k个制约关系，则有个制约关系，则有k条边，中间会存在环条边，中间会存在环分析分析处理环：处理环：l由于环为互为前提，要选择环中的一个必须都进行选择，由于环为互为前提，要选择环中的一个必须都进行选择，因此可以将环缩成一个点，这个点为权值和价值为其他因此可以将环缩成一个点，这个点为权值和价

30、值为其他点的和。点的和。l孤立点没有与其他点也没有任何关系，可以不管。孤立点没有与其他点也没有任何关系，可以不管。l如果把每个连通分量看成一棵树，则图变成了为一个森如果把每个连通分量看成一棵树，则图变成了为一个森林，图林，图2。树型动态规划树型动态规划l显然这个森林可以采用树型动态规划，先将它儿叉树。显然这个森林可以采用树型动态规划，先将它儿叉树。l设设f(i,j)表示以表示以i为根结点的二叉树分配为根结点的二叉树分配j资源的最大价值资源的最大价值根结点不选根结点选),j,(, c)w,(),(max),(rirfirirkjirfkirfjirfrl警卫安排警卫安排l一个有一个有N个区域的树

31、结构上需要安排若干个警卫；个区域的树结构上需要安排若干个警卫；l每个区域安排警卫所需要的费用是不同的；每个区域安排警卫所需要的费用是不同的；l每个区域的警卫都可以望见其相邻的区域，只要一每个区域的警卫都可以望见其相邻的区域，只要一个区域被一个警卫望见或者是安排有警卫，这个区个区域被一个警卫望见或者是安排有警卫，这个区域就是安全的；域就是安全的；l任务：在确保所有区域都是安全的情况下，找到安任务：在确保所有区域都是安全的情况下，找到安排警卫的最小费用；排警卫的最小费用；l0n=720；l分析样例分析样例l该图有该图有6个区域如图个区域如图1，安排情况如图，安排情况如图2，红色点为安排，红色点为安排了警卫。了警卫。l2号警卫可以观察号警卫可以观察1，2，5，6；3号警卫可以观察号警卫可以观察1，3； 4号警卫可以观察号警卫可以观察1，4；l费用：费用：16+5+4=25分析分析l对于每个点对于每个点i，都有，都有3种状态分别为：种状态分别为：l要么在父亲结点安排警卫，即被父亲看到要么在父亲结点安排警卫，即被父亲看到l要么在儿子结点安排警卫，即被儿子看到要么在儿子结点安排警卫，即被儿子看到l要么安排警卫要么安排警卫l对于对于ili被父亲看到，这时被父亲看到，这时i没有安排警卫，没有安排警卫，i的儿子