计算基础教程 9

授课内容动态规划学时4教学目标知识目标理解动态规划的核心思想与基本概念掌握最优子结构、无后效性、公共子问题三大特征掌握数字金字塔、01背包的状态定义与转移方程了解递归、递推及滚动数组优化的实现方式能力目标提升最优解问题的抽象建模与规律分析能力强化状态转移方程的推导与算法设计能力培养动态规划与其他算法择优选用的实践能力重点与难点重点动态规划三大核心特征与适用场景数字金字塔问题的状态转移与求解过程01背包问题的思路与状态转移方程递归、递推与滚动数组优化实现方法难点正确推导状态转移方程并理解其含义掌握01背包一维优化与逆序遍历原理教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述本章承接搜索算法，学习求解最优解问题的高效方法动态规划是竞赛、考级与面试中的最高频考点之一可解决贪心、搜索难以处理的多阶段决策最优问题通过子问题复用与优化，大幅降低时间复杂度本章由浅入深，为后续复杂算法打下核心基础第二部分：新课讲解一、算法概述1、引例：数字金字塔下图是一个数字金字塔，要求寻找一条从最高点到底部任意处的路径，使路径上数字的和最大。每一步可以从当前点走到其左下方或者右下方。2、解题思路正确的解题思路为使用动态规划的思想，从原问题开始，逐步分解成子问题，待子问题求解之后，再逐步返回求出原问题的解，整个过程如下图所示。3、重要概念状态状态是指用于描述在某个阶段所面临的子问题的变量或者参数的集合。以数字金字塔为例，状态可以定义为：dp[i][j]。它表示从第i行第j列的位置出发，到达底部的最大路径和。其中：i表示当前所在的行，j表示当前所在的列。状态转移方程状态转移方程是描述状态之间关系的数学表达式，它定义了如何从一个或多个子问题的解推导出当前问题的解。以数字金字塔为例，其状态转移方程如下：4、动态规划算法与分治算法类似，动态规划的基本思想也是将要求解的问题分解成若干个子问题，先求子问题的解，然后从这些子问题的解得到原问题的解。5、三大特征能够使用动态规划解决的问题，需要具有三大特征：最优子结构、无后效性和公共子问题。最优子结构最优子结构是指原问题的最优解中需要包含其子问题的最优解，或者说原问题的最优解可以由子问题的最优解组合而成。无后效性无后效性是某阶段的状态一旦确定，此后过程的决策不再受此前各种状态及决策的影响。公共子问题在使用递归法自顶向下求解问题时，会产生一些重复的子问题。针对有公共子问题时消除重复求解的方案是使用“备忘录”技术。二、典型例题1、数字金字塔题目见前面的介绍编程模式动态规划类程序都有二种编程模式：递归法和递推法。递归模式递归模式的视角是从顶向下的，即从原问题开始，考虑如何分解成子问题。由于子问题与原问题具有相同的结构，所以可以递归调用原问题的处理函数来处理子问题。金字塔的递归模式核心代码如下：intn; //金字塔行数inta[31][31]; //存储金字塔中的数据intdp[31][31]; //备忘录,使用dp[i][j]保存pyramid(i,j)的返回值intpyramid(inti,intj) //返回从i行j列上的数字开始的最大路径和{ if(dp[i][j]!=-1)returndp[i][j];//此前已记录过参数(i,j)对应的计算结果 if(i==n-1) //已到达最后一行,注意从行号从0算起 dp[i][j]=a[i][j]; else dp[i][j]=a[i][j]+max(pyramid(i+1,j),pyramid(i+1,j+1)); returndp[i][j];}递推模式递推模式的视角是从底向上的，即从最末级的子问题开始，利用它们来推算出一个规模较大一点的子问题的解，然后再利用这些规模较大一点的子问题的解来推算出规模更大的子问题的解，直到推算出原问题的解。金字塔的递推模式核心代码如下：intn; //金字塔行数inta[31][31]; //存储金字塔中的数据intdp[31][31]; //存储递推结果for(inti=n-1;i>=0;i--)//计算最大路径和 for(intj=0;j<=i;j++) { if(i==n-1) dp[i][j]=a[i][j]; else dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]); }再针对剩余数据，重复以上步骤，直到全部数据都有序为止。2、股票买卖题目已知n天中每一天股票的价格，在最多允许买入和卖出股票各一次的情况下，要求计算所能获取的最大利润。注意股票只能先买入后卖出。【输入格式】第一行，一个正整数n，表示天数；1=<n<=105。第二行，n个正整数，表示n天内股票的价格。每个价格不超过104。【输出格式】一个整数，表示最大利润。解析本题中每天都面临二种操作：买入股票和卖出股票。由于不能确定应该买入还是卖出，我们只能在每天都将这二种操作枚举一下。对于买入，需要和之前的买入价格对比一下，如果今天的价格更低，就进行买入，否则不需要买入。因此，我们需要一个变量来记录遇到过的最低价格。对于卖出，我们简单地记录卖出之后能获得的利润即可。如果今天卖出比之前卖出获得的利润更高，就卖出；否则不卖出。程序intn,p;intminPrice=20000000; //最低购入价格intmaxProfit=-1; //最高收益cin>>n;for(inti=0;i<n;i++) //采用递推方式计算最优解{ cin>>p; if(minPrice>p)minPrice=p; //记录遇到过的最低购入价格 if(p-minPrice>maxProfit)maxProfit=p-minPrice; //记录最大收益}cout<<maxProfit<<endl;三、01背包问题1、背包问题概述什么是背包问题背包问题是一个著名的组合优化问题，是动态规划的典型应用之一。背包问题可描述为：有N件物品，每件物品的重量和价值各不相同。现有一个背包，它的容量为W(即装入物品的总重量不超过W)，如何选择装入物品，使背包内物品的价值最大。多种多样的背包问题背包问题有三种基本形式：01背包问题、完全背包问题和多重背包问题。01背包问题是上述三种形式中最简单一种，其特点是有n件物品可供选择，每件物品只能选择一次。因为每件物品要么最终装入背包（记为1），要么不装入背包（记为0），故称为01背包。解法01背包问题可以使用动态规划或搜索来解，其中使用动态规划来解是最优的。2、01背包问题的递归解法思路考虑最后一件物品，它只有放入选与不选二种选择。如果不选，则原问题变为n-1件物品放入背包的最大价值问题。如果选择，则它放入背包之后，背包内的价值增加了，但同时可用容量变小了。原问题变为n-1件物品放入一个容量稍小一些的背包的最大价值问题。状态转移方程用f[i][v]表示前i件物品放入容量为v的背包中的最大价值，则01背包问题的状态转移方程为：f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i])f[i-1][v]：表示第i件物品不装入背包，将背包的容量v全部用于装前i-1件物品时能装入的最大价值。程序intw[30],c[30]; //分别存储每件物品的重量和价值intPackage(intsum,intv,intn){ if(n==1)returnv>=w[0]?sum+c[0]:sum; //仅剩余一件物品时 if(v<w[n-1])returnPackage(sum,v,n-1); //背包装不下第n件物品时 returnmax(Package(sum+c[n-1],v-w[n-1],n-1),Package(sum,v,n-1)); }3、01背包问题的递推解法思路使用递推法的解题过程，相当于在逐行填写如下表所示一张表格。背包容量物品件数123456778101(重量2,价值1）01111111112(重量3,价值4）01445555553(重量4,价值6）4(重量8,价值9）程序intw[31],c[31]; //分别存储每件物品的重量和价值intf[31][201];//f[i][v]表示前i件物品装入容量为v的背包中的最大价值for(inti=1;i<=n;i++) //循环计算每一件物品{for(intv=1;v<=m;v++)if(w[i]<=v)//第i件物能够放入背包内时 f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]);else //第i件物品无法放入背包内时 f[i][v]=f[i-1][v];}4、01背包问题的递推优化解法问题的提出当物品数量n很大时，上面表格会有很多行，要占用大量内存。那么，能否优化一下此表格，以减少内存占用呢？解决方案我们观察单元格的计算公式：f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i])在计算第i行上的数据时，只使用了第i-1行上的数据，第i-2行及之前的行上的数据并没有用到，当然也就不需要存储了。由此，我们可以将表10-1所示的表格压缩为只一行，即简化成了一个一维数组。程序intw[31],c[31]; //分别存储每件物品的重量和价值intf[201]; //滚动数组for