2017-10-30

DAG上的动态规划

这篇博文DAG上的dp分为:
有终点的dp(最优解为dp[T])和无终点的dp(最优的结果最后扫描一遍dp[])，注意状态转移的思想和求最小字典序的贪心思想。
主要就是lrj紫书的笔记吧。

题目

由于NYOJ这个时候挂了。我只能复述一下题意了。

题意

有n个矩形，有长和宽
一个矩形A(a, b), 另外一个矩形B(c, d)。A能嵌套在B中当且仅当a<c&&b<d || a<d&&b<d(注意没有等号)
思考一下如果有等号怎么做？(加一个vis[]数组，防止dfs的时候陷入死循环。)
问最多能嵌套多少个矩形？

题解

方法一

一维排序，另外的一维求最大的上升子序列。由于比较的简单，就不给代码了。

方法二

若矩形A可以嵌套在B中，那么就从A向B连一条边
问题转化为了DAG上面的最长路问题。
状态设置：dp[i]：表示从i号节点开始的最长路。
状态转移方程：dp[i] = max{dp[j]+1|(i, j)\(\subset\)E}.
边界：最大的矩形dp[]=1（代码中不需要额外的设置边界，但是有的题目需要）
结果：max{dp[i]| \(i \in (0, n-1)\)}.编号从0开始

未检测正确性的代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
struct rectangle{
    int id;
    int a, b;
}rect[maxn];
int n;
int G[maxn][maxn];
int dp[maxn];
//bool vis[maxn];
//若相等大小的矩形可以嵌套在一起，那么必须要加一个vis[]标记。因为在
//递归的时候若两个相等的时候，没有加入之前访问的标记，那么就会陷入一个相互嵌套的
//死循环，因此要标记一个已经访问的矩形
int dfs(int u){
    if(dp[u]>0) return dp[u];
    int ans = 1;
    //vis[u] = true;
    for(int i=0; i<n; i++){
        int v = rect[i].id;
        //if(vis[v]) continue;
        if(G[u][v]){
            ans = max(ans, dfs(v)+1);
        }
    }
    return dp[u] = ans;
}
bool cmp(rectangle aa, rectangle bb){
    if((aa.a < bb.a && aa.b<=bb.b)) return true;
    else if(aa.a == bb.a){
        if(aa.b<=bb.b) return true;
    }
    return false;
}
void pint_ans(int u){
}
int main()
{
    while(~scanf("%d", &n)){
        int tot = 0;
        memset(G, 0, sizeof(G));
        memset(vis, 0, sizeof(vis));
        for(int i=0; i<n; i++){
            int a, b;
            scanf("%d%d", &a, &b);
            rect[tot].id = tot;
            if(a<=b){
                rect[tot].a = a;
                rect[tot++].b = b;
            }
            else{
                rect[tot].a = b;
                rect[tot++].b = a;
            }
        }
        for(int i=0; i<tot; i++){
            for(int j=0; j<tot; j++){
                if(i == j) continue;
                if(rect[i].a<rect[j].a && rect[i].b<rect[j].b)
                    G[i][j] = 1;
                else if(rect[i].a<rect[j].b && rect[i].b<rect[j].a)
                    G[i][j] = 1;
            }
        }
        sort(rect, rect+n, cmp);
        for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            printf("%d ", G[i][j]);
        }printf("\n");}
        for(int i=0; i<n; i++){
            printf("%d %d\n", rect[i].a, rect[i].b);
        }
        for(int i=0; i<n; i++){
            int u = rect[i].id;
            dfs(u);
        }
        int ans = -1;
        for(int i=0; i<n; i++){
            ans = max(ans, dp[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

然后我就思考了一下，发现记忆化dp的时候并不需要从较小的矩形开始。从任意的点开始dfs然后记忆化就好了(想象那一棵dfs树)(想想为什么不需要从根部向叶子进行记忆化？因为任何一个子结构一旦被计算完成了，那么后面需要再次计算这样的子结构的时候，不可能会有更优的解，因此不需要更改。总之，一旦子问题探索完，那么dp[i]的值就不会更改。这也是能够记忆化的一个重要的条件)。于是并不需要前面代码记录点的id.
下面是精简后的代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
struct rectagle{
    int a, b;
}rect[maxn];
int n;
bool G[maxn][maxn];
int dp[maxn];
int dfs(int u){
    if(dp[u]>0) return dp[u];
    int ans = 1;
    for(int i=0; i<n; i++){
        if(G[u][i]){
            ans = max(ans, dfs(i)+1);
        }
    }
    return dp[u] = ans;
}
int main()
{
    while(~scanf("%d", &n)){
        memset(G, 0, sizeof(G));
        memset(dp, 0, sizeof(dp));
        for(int i=0; i<n; i++){
            int a, b;
            scanf("%d%d", &a, &b);
            if(a<=b){
                rect[i].a = a;
                rect[i].b = b;
            }
            else {
                rect[i]. a = b;
                rect[i].b = a;
            }
        }
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(i == j) continue;
                if(rect[i].a<rect[j].a&&rect[i].b<rect[j].b) G[i][j] = true;
                else if(rect[i].a<rect[j].b&&rect[i].b<rect[i].a) G[i][j] = true;
            }
        }
        for(int i=0; i<n ;i++){
            dfs(i);
        }
//        for(int i=0; i<n ;i++) printf("%d ", dp[i]);
//        printf("\n");
        int ans = -1;
        for(int i=0; i<n ;i++){
            ans = max(ans, dp[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

打印字典序最小的矩形序号

加一个递归函数：

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

进一步的思考

上面的打印最小字典序很理所当然。那么用我们之前的dp[i]表示以i节点为终点的状态时，就比较的难以打印出来。为什么？
因为按照第一种状态描述的话，搜索的顺序是顺序的。而字典序最小就是一种的顺序的贪心思想。而倒着打印的时候，哪怕后面的额再小，只要前面的很小，那么它就不是最优的。

打印所有的最长路径。

用一个数组来记录。到达终点的时候再打印一条路径。回溯到上一个节点。到达新的终节点的时候再打印路径。
感觉用stack就可以了。

题目

硬币问题

题意

给定目标的总价值S，n种面值的硬币
每种硬币的数目无限

题解

这里以最长路径为例：

确认状态：dp[i]：从i价值到0价值的最长路径
状态转移方程：dp[s] = max{dp[s], dp[s-value[i]]+1|\(i \in (0, n)\)}
边界：dp[0] = 0;
答案：dp[S]

未经证明的代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
const int max_value = 1e4+5;
const int INF = 1e9;
int value[maxn];
int n, S;
int dp[max_value];
int dp2[max_value];
int dfs(int S){
    if(S == 0) return 0;
    if(dp[S]>=0) return dp[S];
    //printf("%d\n", S);
    int ans = INF;
    for(int i=0; i<n; i++){
        if(value[i]<=S)
        ans = min(ans, dfs(S-value[i])+1);
    }
    return dp[S] = ans;
}
int dfs2(int S){
    if(S == 0) return dp2[0] = 0;
    if(dp2[S]>=0) return dp2[S];
    //printf("%d\n", S);
    int ans = -INF;
    for(int i=0; i<n; i++){
        if(value[i]<=S)
        ans = max(ans, dfs2(S-value[i])+1);
    }
    return dp2[S] = ans;
}
int main(){
    while(~scanf("%d%d", &S, &n)){
        memset(dp, -1, sizeof(dp));
        memset(dp2, -1, sizeof(dp));
        for(int i=0; i<n; i++){
            scanf("%d", &value[i]);
        }
        dfs(S);
        dfs2(S);
        printf("最大的数目：%d\n", dp2[S]);
        printf("最小的数目：%d\n", dp[S]);
    }
    return 0;
}

递推版本,字典序最小

#include <bits/stdc++.h>
using namespace std;
/*
15 6
1 2 7 8 12 50
*/
const int maxn = 105;
const int max_value = 1e4+10;
const int INF = 1e9;
int dp[max_value];
int value[maxn];
int n, S;
int maxv[max_value], minv[max_value];
void print_ans(int d[], int S){
    for(int i=0; i<n; i++){
        if(d[S-value[i]]+1 == d[S]){
            printf("%d ", value[i]);
            print_ans(d, S-value[i]);
            break;
        }
    }
}
int main()
{
    while(~scanf("%d%d", &S, &n)){
        memset(dp, -1, sizeof(dp));
        for(int i=0 ;i<n; i++) scanf("%d", &value[i]);
        maxv[0] = minv[0] = 0;
        for(int i=1; i<=S; i++){
            minv[i] = INF;
            maxv[i] = -INF;
        }
        for(int i=1; i<=S; i++){
            for(int j=0; j<n; j++){
                if(value[j]<=i){
                    if(minv[i-value[j]] != INF)
                        minv[i] = min(minv[i], minv[i-value[j]]+1);
                    if(maxv[i-value[j]]!= -INF)
                        maxv[i] = max(maxv[i], maxv[i-value[j]]+1);
                }
            }
        }
        printf("最大需要的硬币数：%d\n", maxv[S]);
        printf("最小需要的硬币数：%d\n", minv[S]);
        print_ans(maxv, S);
        printf("\n");
        print_ans(minv, S);
        printf("\n");
    }
    return 0;
}

非递归打印字典最小序。这在dijkstra里面记录最短路径的道理也是相同的。
用两个数组保存状态

int path_min[max_value];
int path_max[max_value];
void print_ans(int d[], int S){
    while(S){
        printf("%d ", value[d[S]]);//printf("%d ", d[S])是硬币的序号最小值
        S -= value[d[S]];
    }
}
for(int i=1; i<=S; i++){
    for(int j=0; j<n; j++){
        if(value[j]<=i){
            if(minv[i-value[j]] != INF){
                if(minv[i]>minv[i-value[j]]+1){
                    path_min[i] = j;
                    minv[i] = minv[i-value[j]]+1;
                }
            }
            if(maxv[i-value[j]] != -INF){
                if(maxv[i]<maxv[i-value[j]]+1){
                    path_max[i] = j;
                    maxv[i] = maxv[i-value[j]]+1;
                }
            }
        }
    }
}

若j的枚举顺序是从大到小的，那么应该改成下面的带等号。目的是使字典序最小。

1 2	if(minv[i]>=minv[i-value[j]]+1) if(maxv[i]<=maxv[i-value[j]]+1)

未解决的问题

本文标题:DAG上的动态规划

文章作者:Babydragon

发布时间:2017-10-30, 16:18:53

最后更新:2018-03-23, 13:35:35

原始链接:http://baolintian.github.io/2017/10/30/DAG上的动态规划/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

题目

题意

题解

方法一

方法二