DP入门(2)——DAG上的动态规划

时间:2022-06-28 22:44:11

有向无环图(DAG,Directed Acyclic Graph)上的动态规划是学习动态规划的基础。很多问题都可以转化为DAG上的最长路、最短路或路径计数问题。

一、DAG模型

【嵌套矩形问题】

问题:有n个矩形,每个矩形可以用两个整数a、b描述,表示它的长和宽。矩形X(a , b)可以嵌套在矩形Y(c , d)中当且仅当a<c,b<d,或者b<c,a<d(相当于把矩形X旋转90°)。例如(1,5)可以嵌套在(6, 2)内,但不能嵌套在(3, 4)内。你的任务是选出尽可能多的矩形排成一行,使得除了最后一个之外,每个矩形都可以嵌套在下一个矩形内。如果有多解,矩形编号的字典序应尽量小。

分析:矩形之间的“可嵌套”关系是一个典型的二元关系(我的理解是两个矩形之间存在关系),二元关系可以用图来建模。如果矩形X可以嵌套在矩形Y里,就从X到Y连一条有向边。这个有向图必然是无环的,因为一个矩形无法直接或间接地嵌套在自己内部。换句话说,它是一个DAG。这样,所要求的便是DAG上的最长路径。

【硬币问题】

问题:有n种硬币,面值分别为V1, V2, ..., Vn,每种都有无限多。给定非负整数S,可以选用多少个硬币,使得面值之和恰好为S?输出硬币数目的最小值和最大值。1 <= n <= 100, 0 <= S <= 10000, 1 <= Vi <= S。

分析:此问题尽管看上去和嵌套矩形问题很不一样,但本题的本质也是DAG上的路径问题。将每种面值看作一个点,表示“还需要凑足的面值”,则初始状态为S,目标状态为0。若当前在状态 i,每使用一个硬币 j,状态便转移到i - Vj 。

补充:这个模型和上一题类似,但也有一些明显地不同之处:上题并没有确定路径的起点和终点(可以把任意矩形放在第一个和最后一个),而本题的起点必须为S,终点必须为0 。点固定之后“最短路”才是有意义的。在上题中,最短序列显然是空(如果不允许空,就是单个矩形,不管怎样都是平凡的),而本题的最短路径却不容易确定。

二、最长路及其字典序(嵌套矩形)

  如何求DAG中不固定起点的最长路径呢?

  仿照数字三角形的做法,设d(i)表示从结点 i 出发的最长路长度,应该如何写状态转移方程呢?第一步只能走到它的相邻点,因此:d(i)= max{d(j)+1} ,(i , j)∈E,E为边集。则最终答案是所有d(i)中的最大值。

  有条理地列下来就是:

  • 状态:d(i)
  • 状态转移方程:d(i)= max{d(j)+1}

  我们可以使用递推或记忆化搜索的方法计算状态转移方程。不管使用哪种方法,我们都要先把图建立出来,假设用邻接矩阵保存在矩阵G中(一定要确保建图过程正确无误)。

  我们在此以记忆化搜索的方法求解,下面给出记忆化搜索程序(调用前需初始化d数组的所有值为0):

int dp(int i)
{
int& ans = d[i]; //为表项d[i]声明一个引用ans
if(ans > 0) return ans;
ans = 1;
for(int j=1;j<n;j++){
if(G[i][j]){
ans = max(ans,dp(j)+1);
}
}
return ans;
}

  这里使用了一个技巧——为表项d[i]声明一个引用ans。这样,任何对ans的读写实际上都是在对d[i]进行。当d[i]换成d[i][j][k][l][m][n]这样很长的名字时,该技巧的优势就会很明显。

  提示:在记忆化搜索中,可以为正在处理的表项声明一个引用,简化对它的读写操作。

  原题还有一个要求:如果有多个最优解,矩形编号的字典序应最小。

  我们可以将所有d值计算出来以后,选择最大d[i]所对应的i。如果有多个i,则选择最小的i,这样才能保证字典序最小。接下来可以选择d(i)= d(j)+1 且(i , j)∈ E的任何一个 j 。为了让方案的字典序最小,应选择其中最小的 j 。程序如下:

void print_ans(int i){
printf("%d ",i);
for(int j=1;j<=n;j++){
if(G[i][j] && d[i]==d[j]+1){
print_ans(j);
break;
}
}
}

  提示:根据各个状态的指标值可以依次确定各个最优方案,从而构造出完整方案。由于决策是依次确定的,所以很容易按照字典序打印出所有方案。

  注意,当找到一个满足d[i]= d[j]+1的结点j后就应立刻递归打印从j开始的路径,并在递归返回后退出循环。如果要打印出所有方案,只把break语句删除是不够的。正确的方法是记录路径上的所有点,在递归结束时才一次性输出整条路径。程序可以自行编写。

  有趣的是,如果把状态定义成“d(i)表示以结点i为终点的最长路径长度”,也能顺利求出最优值,却难以打印出字典序最小的方案。想一下,为什么?

三、固定终点的最长路和最短路——硬币问题

  最长路和最短路的求法是类似的,下面只考虑最长路。

  由于终点固定,d(i)的确切含义变为“从结点i出发到结点0的最长路径长度”。下面是求最长路的代码:

int dp(int S)
{
int& ans = d[S];
if(ans >= 0) return ans;
ans = 0;
for(int i=1;i<=n;i++){
if(S >= V[i]) ans = max(ans,dp(S-V[i])+1);
}
return ans;
}

/*  注意到区别了吗?由于在本题中,路径长度是可以为0的(S本身可以是0),所以不能再用d=0表示“这个d值还没有算过”。相应地,初始化时也不能再把d全设为0,而要设置为一个负值——在正常情况下是取不到的。常见的方法是用-1来表示“没有算过”,则初始化时只需用memset(d,-1,sizeof(d))即可。至此,已完整解释了上面的代码为什么把if(ans>0)改成了if(ans>=0)。

  提示:当程序中需要用到特殊值时,应确保该值在正常情况下不会被取到。这不仅意味着特殊值不能有“正确的理解方式”,而且也不能在正常运算中“意外得到”。*/

  其实,上述代码有一个致命的错误,即由于结点S不一定真的能到达结点0,所以需要用特殊的d[S]值表示“无法到达”,但在上述代码中,如果S根本无法继续往前走,返回值是0,将被误以为是“不用走,已经到达终点”的意思。如果把ans初始化为-1呢?别忘了-1代表“还没算过”,所以返回-1相当于放弃了自己的劳动成果。如果把ans初始化为一个很大的整数呢(我觉得只要<-1就行了)?从目前来看,它也会被认为是“还没算过”,但至少可以和所有d的初值分开——只需把代码中if(ans>=0)改为if(ans!=-1)即可,如下所示:

int dp(int S)
{
int& ans = d[S];
if(ans != -1) return ans;
ans = -(1<<30);
for(int i=1;i<=n;i++){
if(S >= V[i]) ans = max(ans,dp(S-V[i])+1);
}
return ans;
}

  提示:在记忆化搜索中,如果用特殊值表示“还没算过”,则必须将其和其他特殊值(如无解)区分开。

  上述错误是很常见的,意识到这些问题,寻求解决方案是不难的,但就怕调试很久以后仍然没有发现是哪里出了问题。

  另一个解决方法是不用特殊值表示“还没算过”,而用另外一个数组vis[i]表示状态i是否被访问过,如下所示:

int dp(int S)
{
if(vis[S]) return d[S];
vis[S] = -1;
int& ans = d[S];
ans = -(1<<30);
for(int i=1;i<=n;i++){
if(S >= V[i]) ans = max(ans,dp(S-V[i])+1);
}
return ans;
}

  尽管多了一个数组,但可读性增强了许多:再也不用担心特殊值之间的冲突了,在任何情况下,记忆化搜索的初始化都可以用memset(vis,0,sizeof(vis))实现。

  提示:在记忆化搜索中,可以用vis数组记录每个状态是否计算过,以占用一些内存为代价增强程序的可读性,同时减少出错的可能。

  本题要求最小、最大两个值,记忆化搜索就必须写两个。在这种情况下,用递推更加方便(此时需注意递推的顺序):

minv[0] = maxv[0] = 0;
for(int i=1;i<=S;i++){
minv[i] = INF;    //minv[i]表示最小值
maxv[i] = -INF;    //maxv[i]表示最大值
}
for(int i=1;i<=S;i++){
for(int j=1;j<=n;j++){
if(i >= V[j]){
minv[i] = min(minv[i],minv[i-V[j]]+1);
maxv[i] = max(maxv[i],maxv[i-V[j]]+1);
}
}
}
printf("%d %d\n",minv[S],maxv[S]);

  如何输出字典序最小的方案呢?刚刚介绍的方法仍然适用,如下所示:

void print_ans(int* d,int S)
{
for(int i=1;i<=n;i++){
if(S>=V[i] && d[S]==d[S-V[i]]+1){
printf("%d ",i);
print_ans(d,S-V[i]);
break;
}
}
}

  然后分别调用print_ans(min,S)(注意在后面要加一个回车符)和print_ans(max,S)即可。输出路径部分和上题的区别是,上题打印的是路径上的点,而这里打印的是路径上的边。

  提示:当用递推法计算出各个状态的指标之后,可以用与记忆化搜索完全相同的方式打印方案。

  很多用户喜欢另外一种打印路径的方法:递推时直接用min_coin[S]记录满足min[S]==min[S-V[i]]+1的最小的i,则打印路径时可以省去print_ans函数中的循环,并可以方便地把递归改成迭代(当然,原来的也可以改成迭代,但不那么自然)。具体来说,需要把递推过程改写成以下形式:

for(int i=1;i<=S;i++){
for(int j=1;j<=n;j++){
if(i >= V[j]){
if(min[i]>min[i-V[j]]+1){
min[i] = min[i-V[j]]+1;
min_coin[i] = j;
}
if(max[i]<max[i-V[j]]+1){
max[i] = max[i-V[j]]+1;
max_coin[i] = j;
}
}
}
}

  注意,判断中用的是“>”和“<”,而不是“>=”和“<=”,原因在于“字典序最小解”要求当min/max值相同时取最小的i值。反过来,如果j是从大到小枚举的,就需要把“>”和“<”改成“>=”和“<=”才能求出字典序最小解。

  在求出min_coin和max_coin之后,只需调用print_ans(min_coin,S)和print_ans(max_coin,S)即可。

void print_ans(int* d,int S)
{
while(S){
printf("%d ",d[S]);
S -= V[d[S]];
}
}

  该方法是一个“用空间换时间”的经典例子——用min_coin和max_coin数组消除了原来print_ans中的循环。

  提示:无论是用记忆化搜索还是递推,如果在计算最优值的同时“顺便”算出各个状态下的第一次最优决策,则往往能让打印方案的过程更加简单、高效。

四、小结

  本节介绍了动态规划的经典应用:DAG中的最长路和最短路。

  和上一篇讲述的数字三角形一样,DAG的最长路和最短路都可以用记忆化搜索和递推两种实现方式。打印解时既可以根据d值重新计算出每一步的最优决策,也可以在动态规划时“顺便”记录下每步的最优决策。

  由于DAG最长(短)路的特殊性,有两种“对称”的状态定义方式。

  • 状态1:设d(i)为从 i 出发的最长路,则d(i)= max{d(j+1)},(i , j)∈E。
  • 状态2:设d(i)为以 i 结束的最长路,则d(i)= max{d(j+1)},(j , i)∈E。

  如果使用状态2,“硬币问题”就变得和“嵌套矩形问题”几乎一样了(唯一的区别是“嵌套矩形问题”还需要取所有d(i)的最大值)!我们在上面介绍了比较麻烦的状态1,主要是为了展示一些常见技巧和陷阱,实际比赛中不推荐使用。

  使用状态2时,有时还会遇到一个问题:状态转移方程可能不好计算,因为在很多时候,可以方便地枚举从某个结点i出发的所有边(i , j),却不方便“反着”枚举(j , i)。特别是在有些题目中,这些边具有明显的实际背景,对应的过程不可逆。这时需要用“刷表法”。

  什么是“刷表法”呢?传统的递推法可以表示成“对于每个状态 i,计算f(i)”,或者称为“填表法”。这需要对于每个状态 i,找到f(i)依赖的所有状态,在某些情况下并不方便。另一种方法是“对于每个状态i,更新f(i)所影响到的状态”,或者称为“刷表法”。对应到DAG最长路的问题中,就相当于按照拓扑序枚举 i,对于每个 i,枚举边(i , j),然后更新d[j] = max(d[j],d[i]+1)。注意,一般不把这个式子叫做“状态转移方程”,因为它不是一个可以直接计算d[j]的方程,而只是一个更新公式。

  提示:传统的递推法可以表示成“对于每个状态 i,计算f(i)”,或者称为“填表法”。这需要对于每个状态 i,找到f(i)依赖的所有状态,在某些时候并不方便。另一种方法是“对于每个状态 i,更新f(i)所影响到的状态”,或者称为“刷表法”,有时比填表法方便。但需要注意的是,只有当每个状态所依赖的状态对它的影响相互独立时才能用刷表法。

DP入门(2)——DAG上的动态规划的更多相关文章

  1. UVA 1025 &quot&semi;A Spy in the Metro &quot&semi; (DAG上的动态规划?? or 背包问题??)

    传送门 参考资料: [1]:算法竞赛入门经典:第九章 DAG上的动态规划 题意: Algorithm城市的地铁有 n 个站台,编号为 1~n,共有 M1+M2 辆列车驶过: 其中 M1 辆列车从 1 ...

  2. UVa 103 Stacking Boxes --- DAG上的动态规划

    UVa 103 题目大意:给定n个箱子,每个箱子有m个维度, 一个箱子可以嵌套在另一个箱子中当且仅当该箱子的所有的维度大小全部小于另一个箱子的相应维度, (注意箱子可以旋转,即箱子维度可以互换),求最 ...

  3. DAG上的动态规划之嵌套矩形

    题意描述:有n个矩形,每个矩形可以用两个整数a.b描述,表示它的长和宽, 矩形(a,b)可以嵌套在矩形(c,d)当且仅当a<c且b<d, 要求选出尽量多的矩形排成一排,使得除了最后一个外, ...

  4. 第九章(二)DAG上的动态规划

    DAG上的动态规划: 有向无环图上的动态规划是学习DP的基础,很多问题都可以转化为DAG上的最长路.最短路或路径计数问题. 1.没有明确固定起点重点的DAG模型: 嵌套矩形问题:有n个矩形,每个矩形可 ...

  5. DAG 上的动态规划(训练指南—大白书)

    有向无环图(DAG,Directed Acyclic Graph)上的动态规划是学习动态规划的基础.很多问题都可以转化为DAG上的最长路.最短路或路径计数问题. 一.矩形嵌套 题目描述:       ...

  6. 嵌套矩形——DAG上的动态规划

    有向无环图(DAG,Directed Acyclic Graph)上的动态规划是学习动态规划的基础.非常多问题都能够转化为DAG上的最长路.最短路或路径计数问题. 题目描写叙述: 有n个矩形,每一个矩 ...

  7. DAG上的动态规划---嵌套矩形(模板题)

    一.DAG的介绍 Directed Acyclic Graph,简称DAG,即有向无环图,有向说明有方向,无环表示不能直接或间接的指向自己. 摘录:有向无环图的动态规划是学习动态规划的基础,很多问题都 ...

  8. UVA 437 The Tower of Babylon(DAG上的动态规划)

    题目大意是根据所给的有无限多个的n种立方体,求其所堆砌成的塔最大高度. 方法1,建图求解,可以把问题转化成求DAG上的最长路问题 #include <cstdio> #include &l ...

  9. The Tower of Babylon UVA - 437 DAG上的动态规划

    题目:题目链接 思路:每个方块可以用任意多次,但因为底面限制,每个方块每个放置方式选一个就够了,以x y为底 z 为高,以x z为底 y 为高,以y z为底 x为高,因为数据量很小,完全可以把每一种当 ...

随机推荐

  1. dataGridViewX和数据库的链接之dataGridViewX1&period;DataSource &equals; ds&period;Tables&lbrack;0&rsqb;&semi;

    dataGridViewX1.DataSource = ds.Tables[0]; 1, dataGridViewX和数据库链接,如果我们用 dataGridViewX1.DataSource = d ...

  2. Scanner 和 String 类的常用方法

    Scanner类是在jdk1.5 之后有了这个: 常用格式是: Scanner sc = new Scanner(System.in); 从以下版本开始: 1.5 构造方法摘要 Scanner(Fil ...

  3. Selenium firefox 版本问题

    问题:Unable to connect to host 127.0.0.1 on port 7055 after 45000 ms 原因: selenium-server-standalone-x. ...

  4. 阿里云centos下安装nginx、jdk、tomcat、绑定域名、解析域名

    1.ESC后安全设置(管理控制台->本实例安全组->配置规则->添加安全组规则->3306.80端口配置) 2.nginx  安装,首先安装三大件  PCRE.zlib.ope ...

  5. 还在繁琐的敲MVP接口和实现类吗,教你一秒搞定。

    只有程序员懒起来,才能提高开发效率 233333 在MVP的使用过程中,我们需要反复的去写各种MVP的接口和实现类, 实在是 太麻烦了!!所以抽时间撸了一款插件(只可用于Intellj IDEA 和 ...

  6. Master-Worker设计模式介绍

    Master-Worker模式是常用的并行设计模式.核心思想是,系统由两个角色组成,Master和Worker,Master负责接收和分配任务,Worker负责处理子任务.任务处理过程中,Master ...

  7. 七、Builder 建造器模式

    需求:需要组装复杂结构的实例 代码清单: Builder 接口: public abstract class Builder { public abstract void makeTitle(Stri ...

  8. Delphi:程序自己删除自己,适用于任何windows版本&lpar;含源码&rpar;

    Delphi:程序自己删除自己,适用于任何windows版本(含源码) function Suicide: Boolean; var   sei: TSHELLEXECUTEINFO;   szMod ...

  9. php递归函数细节

    <?php /** *php递归函数细节 *从1到5的阶乘 * */ header("Content-Type:text/html;charset=utf-8"); func ...

  10. webpack的安装与使用(单文件)

    在安装 Webpack 前,你本地环境必须已安装nodejs. 可以使用npm安装,当然由于 npm 安装速度慢,也可以使用淘宝的镜像及其命令cnpm(npm install -g cnpm --re ...