Dotcpp  >  编程教程  >  动态规划  >  DAG上的DP实例讲解

DAG上的DP实例讲解

点击打开在线编译器,边学边练

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

两个经典的DAG模型,嵌套矩形和硬币问题


一、嵌套矩形

(1)第一个DAG模型:矩形嵌套问题

描述:有n个矩形,每个矩形可以用a,b来描述,表示长和宽。

矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a<c,b<d或者b<c,a<d(相当于旋转X90度)。

例如(1,5)可以嵌套在(6,2)内,但不能嵌套在(3,4)中。

你的任务是选出尽可能多的矩形排成一行,使得除最后一个外,每一个矩形都可以嵌套在下一个矩形内。

【分析】

矩形间的“可嵌套”关系是一个典型的二元关系,二元关系可以用图来建模。如果矩形X可以嵌套在Y中,则就从X到Y连一条有向边。这个图是无环的,因为一个矩形无法直接或或间接的嵌套在自己的内部。也即是说这是以一个DAG。

因此,我们就是在求DAG上的最长路径。

【问题】

这个是一个没有确定的路径起点和终点(可以把任意的矩形放在任何位置)的DAG问题。

如何求解,仿照上次的数字三角形(数塔)问题的求解,可以设d(i)表示从节点i出发的最长路的长度,如何写出状态转移方程呢?第一步只能走到他的相邻的节点,因此:

d(i)= max { d(j)+1 | i, j ∈E }

其中,E为边集。最终答案是所有的d(i)中的最大值。因此可以用递推或者记忆化搜索计算。


(2)解决步骤

第一步,建图。假如用邻接矩阵将矩形间的关系保存在矩阵G中。

第二步,编写记忆化搜索程序(调用前先初始化数组为0)。

第三步,按字典序输出最佳的方案


(3)实例实践

假如有这样的五个矩形:

输入的边长分别是:

矩形宽矩形长
35
46
23
74
66

其DAG表示如下:

DAG表示

由图可知,最长路有3--1--2 和 3--1--4

按字典序之后只有 3--1--2

具体的代码如下:(c语言实现DAG矩形嵌套问题)

/***** DP初步之DAG ********/
 
/******** written by C_Shit_Hu ************/
 
动态规划入门///
 
/****************************************************************************/
/* 
第一个DAG模型:矩形嵌套问题
描述
有n个矩形,每个矩形可以用a,b来描述,表示长和宽。
矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a<c,b<d或者b<c,a<d(相当于旋转X90度)。
例如(1,5)可以嵌套在(6,2)内,但不能嵌套在(3,4)中。
你的任务是选出尽可能多的矩形排成一行,使得除最后一个外,每一个矩形都可以嵌套在下一个矩形内。
输入
测试数据的第一行是一个正正数n,表示该组测试数据中含有矩形的个数(n<=1000)
随后的n行,每行有两个数a,b(0<a,b<100),表示矩形的长和宽
输出
每组测试数据都输出一个数,表示最多符合条件的矩形数目,每组输出占一行
*/
/****************************************************************************/
 
 
// 思路:先对长和宽来此排序,再按照要求构图,
// 完成之后,直接记忆化搜索,值得注意的地方是你不能只从第一个点搜索,而是要从每个点搜索
 
#include<stdio.h>
#include<string.h>
 
#define MAXN 101
int n, G[MAXN][MAXN];     // 图的存储
int x[MAXN], y[MAXN], d[MAXN];  // 节点
 
//记忆化搜索来完成的动态转移
int dp(int i) 
{       
	int j;
	if(d[i] > 0) 
		return d[i];  // 如果已经计算过,直接返回其值
 
	d[i] = 1;         // 否则,置一,递推计算
	for(j = 1; j <= n; j++)
		if(G[i][j])   // 如果图存在,即是满足可嵌套
			if(d[i] <=dp(j)+1)     // 如果存在可嵌套的节点d(j)加一后其值大于d(i)
				d[i]=dp(j)+1;      // 则使d[i]更新
 
			return d[i];       // 返回d[i]
}
 
//按字典序只输出排序最小的序列
/*
此部分的原理:字典序只是消除并列名次的方法,我们最根本的任务还是求出最长路
在把所有的d值计算出来后,选择最大的d[i]所对应的i。而如果有多个i,则选择最小的i,这样保证字典序最小。
接下来选择d(i) = d(j) +1 且i, j ∈E 的任何一个j,但是为满足字典序最小,需选择最小的j
*/
void print_ans(int i) 
{   
	int j;
	printf("%d ", i);    // 第一次i代表最长路的起点节点,以后均代表从该节点开始的路径
	for(j = 1; j <= n; j++) 
		if(G[i][j] && d[i] == d[j]+1)  // 如果该图满足可嵌套,且d[i] = d[j] +1
		{
			print_ans(j);           // 立即输出从节点j开始的路径
			break;
		}
}
 
int main() 
{
	int i, j, t, ans, best;
	scanf("%d", &n);            // n表示矩形的数目
	// 初始化矩形长宽参数,并初次调整长宽顺序
	for(i = 1; i <= n; i++) 
	{
		scanf("%d%d", &x[i], &y[i]);     // 依次输入矩形的边长信息
		if(x[i] > y[i]) 
		{
			t = x[i]; x[i] = y[i]; y[i] = t;   // 保证X[]存的是长,Y[]存的是宽
		}
	}
	memset(G, 0, sizeof(G));  // 数组清零
	for(i = 1; i <= n; i++)           // 建图
		for(j = 1; j <= n; j++)
			if(x[i] < x[j] && y[i] < y[j]) G[i][j] = 1;  // 如果第i个矩形的长宽均小于第j个,使图相应的值为1
			
			ans = 0;
			for(i = 1; i <= n; i++)      // 依次递推所有的的节点
				if(dp(i) > ans) 
				{
					best = i;       // best 是最小字典序
					ans = dp(i);
				}
				printf("ans=%d\n", ans);   // 表示最长路长度
				print_ans(best);
				printf("\n");
				while(1);
			return 0 ;
}
 
/******************************************************/
/********************  心得体会  **********************/
/*
好好学习DP!!!
*/
/******************************************************/


二、硬币问题DP

【问题描述】

有n种硬币,面值分别为V1,V2,V3,.....Vn,每种都有无限多。

给定非负整数S,可以选用多少个硬币,使得面值之和恰好为S?

输出硬币数目的最小值和最大值。1<=n>=100, 0<=S<=10000,1<=Vi<=S.


【分析与思路】

思路:本题是固定终点和起点的DAG动态规划。

我们把每种面值看做一个点,表示“还需要凑足的面值”,则初始状态为S,目标状态为0。

如当前在状态i,没使用一个硬币j,状态变转移到i-Vj。

有n种硬币,面值分别为V1,V2,V3,.....Vn,每种都有无限多。

给定非负整数S,可以选用多少个硬币,使得面值之和恰好为S?

输出硬币数目的最小值和最大值。1<=n>=100, 0<=S<=10000,1<=Vi<=S.


本题是固定终点和起点的DAG动态规划。

我们把每种面值看做一个点,表示“还需要凑足的面值”,则初始状态为S,目标状态为0。

如当前在状态i,没使用一个硬币j,状态变转移到i-Vj。

递推方法实现
#include<stdio.h>
#include<string.h>
#define MAX 10001
#define INF  1000000000;
int n, S;
int V[MAX] ,vis[MAX], d[MAX];
int max[MAX], min[MAX] ;
 
// 输出最小字典序
void prit_ans(int *d, int S)
{
    int i;
    for( i=1; i<=n; i++)
        if (S>=V[i] && d[S] == d[S-V[i]] +1)
        {
            printf("%d ", i);
            prit_ans(d, S-V[i]) ;
            break ;
        }
}
 
// 主函数、递推实现最短路最长路
int main ()
{
    memset(min,0,sizeof(min));
    memset(max,0,sizeof(max));
    memset(V,0,sizeof(V));
    int i ,j ;
    min[0] = max[0] = 0;
    printf("请输入要组成的面值之和S:");
    scanf("%d", &S) ;
    printf("请输入不同面值的硬币的种类:");
    scanf("%d", &n) ;
    printf("请输入各个种类的硬币的面值:\n");
    for (i=1; i<=n; i++)
    {
        scanf("%d", &V[i]);
    }
    // 递推算法求解最长最短路
    for (i=1; i<=S; i++)///初始化min初始化为最大值,max初始化为最小值
    {
        min[i] = INF;
        max[i] = -INF;
    }
    for (i=1; i <= S; i++)///表示的钱数
        for (j=1; j<=n; j++)///对应的个数
            if(i >= V[j])///当需要表示的钱币数大于硬币所能表示的数值时,才可以往下进行
            {
                ///对min和max进行更新
                if (min[i] >= (min[i-V[j]] +1))
                    min[i] = min[i-V[j]] +1;
                if (max[i] <= (max[i-V[j]] +1))
                    max[i] = max[i-V[j]] +1;
            }
    printf("%d %d\n", min[S], max[S]);
    //	输出最优字典序
    prit_ans(min, S);
    printf("\n");
    prit_ans(max, S) ;
    printf("\n");
 
    return 0 ;
}

记忆化搜索方法实现。里面加标记的地方为输出字典序最小的序列

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
 
using namespace std;
struct data
{
    int x;
    int y;
} a[1010];
int G[1010][1010];
int dp[1010];
int n;
 
int d(int i)
{
    int& ans = dp[i];
    if(ans > 0)
        return ans;
    ans = 1;
    for(int j = 0; j < n; j ++)
        if(G[i][j])
            ans = max(ans,d(j) + 1);
    return ans;
}
/*
void print_ans(int i)
{
    printf("%d ",i);
    for(int j = 1; j <= n; j ++)
        if(G[i][j] && dp[i] == dp[j]+1)
        {
            print_ans(j);
            break;
        }
}
*/
int main()
{
    int t;
    scanf("%d",&t);
    while(t --)
    {
        memset(dp,0,sizeof(dp));
        memset(G,0,sizeof(G));
        scanf("%d",&n);
        for(int i = 0; i < n; i ++)
            scanf("%d%d",&a[i].x,&a[i].y);
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < n; j ++)
                if(a[j].x < a[i].x && a[j].y < a[i].y || (a[j].y < a[i].x && a[j].x < a[i].y))
                    G[i][j] = 1;
        int maxx = -1,k;
        for(int i = 0; i < n; i ++)
        {
            int t = d(i);
            if(maxx < t)
            {
                k = i;
                maxx = t;
            }
        }
        cout << maxx << endl;
        //print_ans(k);
    }
    return 0;
}



知识点标签:动态规划


本文固定URL:https://www.dotcpp.com/course/985

算法竞赛教程
第一章 算法基础
第二章 搜索算法
第三章 排序算法
第四章 字符串相关
第五章 数学相关
第六章 动态规划
第七章 数据结构
第八章 图论
第九章 计算几何
第十章 其他算法
Dotcpp在线编译      (登录可减少运行等待时间)