动态规划 DP

zifuneko · 2024-08-20 15:59:28 · 算法·理论

之前DP学的超级差喵！这算是复习又是学习。

参考wiki：https://oiwiki.com/dp/

基础

引入

P1216 [IOI 1994 / USACO1.5] 数字三角形 Number Triangles （选自OIwiki）

最简单粗暴的思路是尝试所有的路径。因为路径条数是 指数O(2^r) 级别的，这样的做法无法接受。

注意到这样一个事实，一条最优的路径，它的每一步决策都是最优的。

而对于每一个点，它的下一步决策只有两种：往左下角或者往右下角（如果存在）。因此只需要记录当前点的最大权值，用这个最大权值执行下一步决策，来更新后续点的最大权值。（无后效性）

这样做还有一个好处：我们成功缩小了问题的规模，将一个问题分成了多个规模更小的问题。要想得到从顶端到第 r 行的最优方案，只需要知道从顶端到第 r-1 行的最优方案的信息就可以了。

这时候还存在一个问题：子问题间重叠的部分会有很多，同一个子问题可能会被重复访问多次，效率还是不高。解决这个问题的方法是把每个子问题的解存储下来，通过记忆化的方式限制访问顺序，确保每个子问题只被访问一次。

上面就是动态规划的一些基本思路。

#include<bits/stdc++.h>
using namespace std;

int a[1005][1005];
int main()
{
    int r; cin >> r;
    for(int i=1; i<=r; i++)
        for(int j=1; j<=i; j++)
            cin >> a[i][j];

    // 当前节点的值就等于当前节点加上下面两个节点的最大值
    for(int i=r; i>=1; i--)
        for(int j=1; j<=i; j++)
            a[i][j] += max(a[i+1][j], a[i+1][j+1]);

    cout << a[1][1];
    return 0;
}

原理

能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。

对于一个能用动态规划解决的问题，一般采用如下思路解决：

• 将原问题划分为若干 阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为 状态）；
• 寻找每一个状态的可能 决策，或者说是各状态间的相互转移方式（用数学的语言描述就是 状态转移方程）。
• 按顺序求解每一个阶段的问题。

记忆化搜索

记忆化搜索是一种通过记录已经遍历过的状态的信息，从而避免对同一状态重复遍历的搜索实现方式。

因为记忆化搜索确保了每个状态只访问一次，它也是一种常见的动态规划实现方式。

在求解动态规划的问题时，记忆化搜索与递推的代码，在形式上是高度类似的。这是由于它们使用了相同的状态表示方式和类似的状态转移。也正因为如此，一般来说两种实现的时间复杂度是一样的。

在求解动态规划的问题时，记忆化搜索和递推，都确保了同一状态至多只被求解一次。而它们实现这一点的方式则略有不同：递推通过设置明确的访问顺序来避免重复访问，记忆化搜索虽然没有明确规定访问顺序，但通过给已经访问过的状态打标记的方式，也达到了同样的目的。

与递推相比，记忆化搜索因为不用明确规定访问顺序，在实现难度上有时低于递推，且能比较方便地处理边界情况，这是记忆化搜索的一大优势。但与此同时，记忆化搜索难以使用滚动数组等优化，且由于存在递归，运行效率会低于递推。因此应该视题目选择更适合的实现方式。

背包 DP

01 背包

状态转移方程

由于每个物体只有两种可能的状态（取与不取），对应二进制中的 0 和 1，这类问题便被称为「0-1 背包问题」。

已知条件有第 i 个物品的重量 w_{i}，价值 v_{i}，以及背包的总容量 W。

设 DP 状态 f_{i,j} 为：在只能放前 i 个物品的情况下，容量为 j 的背包所能达到的最大总价值。

考虑转移。假设当前已经处理好了前 i-1 个物品的所有状态，那么对于第 i 个物品，当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为 f_{i-1,j}；当其放入背包时，背包的剩余容量会减小 w_{i}，背包中物品的总价值会增大 v_{i}，故这种情况的最大价值为 f_{i-1,j-w_{i}}+v_{i}。

由此可以得出状态转移方程：

滚动数组优化

由于对 f_i 有影响的只有 f_{i-1}，可以去掉第一维，直接用 f_{i} 来表示处理到当前物品时背包容量为 i 的最大价值，得出以下方程：

仔细观察代码可以发现：对于当前处理的物品 i 和当前状态 f_{i,j}，在 j\geqslant w_{i} 时，f_{i,j} 是会被 f_{i,j-w_{i}} 所影响的。

为了避免这种情况发生，我们可以改变枚举的顺序，从 W 枚举到 w_{i}，这样就不会出现上述的错误，因为 f_{i,j} 总是在 f_{i,j-w_{i}} 前被更新。

#include<bits/stdc++.h>
using namespace std;

const int MAX = 1e5+5;
int n, W, w[MAX], v[MAX], f[MAX];

int main()
{
    cin >> n >> W;
    for(int i=1; i<=n; i++) cin >> w[i] >> v[i];

    // 在只能放前 $i$ 个物品的情况下，容量为 $j$ 的背包所能达到的最大总价值。
    for(int i=1; i<=n; i++)
        for(int j=W; j>=w[i]; j--)
            f[j] = max(f[j], f[j - w[i]] + v[i]);

    cout << f[W];
    return 0;
}

完全背包

0-1 背包类似，在于一个物品可以选取无限次，而非仅能选取一次。

设 f_{i,j} 为只能选前 i 个物品时，容量为 j 的背包可以达到的最大价值。

P1616 疯狂的采药

#include<bits/stdc++.h>
using namespace std;

const int MAXW = 1e7+5;
const int MAXN = 1e5+5;
int n, W, w[MAXN], v[MAXN];
long long f[MAXW];

int main()
{
    cin >> W >> n;
    for(int i=1; i<=n; i++) cin >> w[i] >> v[i];

    // $f(i, j)$ 为只能选前 $i$ 个物品时，容量为 $j$ 的背包可以达到的最大价值。
    for(int i=1; i<=n; i++)
        for(int j=w[i]; j<=W; j++)
            f[j] = max(f[j], f[j - w[i]] + v[i]);

    cout << f[W];
    return 0;
}

多重背包

朴素实现

多重背包也是 0-1 背包的一个变式。与 0-1 背包的区别在于每种物品有 k_i 个，而非一个。

一个很朴素的想法就是：把「每种物品选 k_i 次」等价转换为「有 k_i 个相同的物品，每个物品选一次」。这样就转换成了一个 0-1 背包模型，套用 0-1 背包方法就可解决。

时间复杂度 O(W\sum_{i=1}^nk_i)。

二进制分组优化

二进制拆分是一种将大数字拆分成 2 的幂次方组合的技术，主要用于优化多重背包问题。

通过二进制拆分，我们只需要 \log m 个物品就能表示出 0-m 的所有选择！

注意：拆分后 \text{cnt} 存储的是所有物品拆分表示的 v 和 w 的总数量，这样可以表示物品选取的所有可能，并把时间复杂度从 O(k) 降为 O(\log k)，且将问题转化为了01背包.

P1776 宝物筛选

#include<bits/stdc++.h>
using namespace std;

const int MAX = 2e6+5;
int w[MAX], v[MAX], f[MAX];

int main()
{
    int n, W; cin >> n >> W;

    int cnt = 0; // 二进制分组后的物品数量
    for(int i=1; i<=n; i++)
    {
        int v_i, w_i, m_i; 
        cin >> v_i >> w_i >> m_i;
        for(int j=1; j<=m_i; j<<=1) // 二进制分组优化
            v[++cnt] = j * v_i, w[cnt] = j * w_i, m_i -= j;
        if(m_i) v[++cnt] = v_i * m_i, w[cnt] = w_i * m_i; // 剩余部分
    }

    // 01背包求解
    for(int i=1; i<=cnt; i++)
        for(int j=W; j>=w[i]; j--)
            f[j] = max(f[j], f[j - w[i]] + v[i]);

    cout << f[W];
    return 0;
}

混合背包

P1833 樱花

混合背包就是将前面三种的背包问题混合起来，有的只能取一次，有的能取无限次，有的只能取 k 次。

#include<bits/stdc++.h>
using namespace std;

const int MAX = 1e7+5;
int n, w[MAX], v[MAX], f[MAX], type[MAX];

int main()
{
    int sh, sm, eh, em;
    scanf("%d:%d %d:%d %d", &sh, &sm, &eh, &em, &n);
    int W = (eh * 60 + em) - (sh * 60 + sm);

    int cnt = 0; // 二进制分组后的物品数量
    for(int i=1; i<=n; i++)
    {
        int w_i, v_i, m_i; 
        cin >> w_i >> v_i >> m_i;
        if(m_i == 0) {type[++cnt] = 1, v[cnt] = v_i, w[cnt] = w_i; continue;} 
        if(m_i == 1) {type[++cnt] = 0, v[cnt] = v_i, w[cnt] = w_i; continue;}
        for(int j=1; j<=m_i; j<<=1) // 二进制分组优化
            type[++cnt] = 0, v[cnt] = j * v_i, w[cnt] = j * w_i, m_i -= j;
        if(m_i) type[++cnt] = 0, v[cnt] = v_i * m_i, w[cnt] = w_i * m_i; // 剩余部分
    }

    for(int i=1; i<=cnt; i++)
    {
        if(type[i]) // 完全背包
            for(int j=w[i]; j<=W; j++)
                f[j] = max(f[j], f[j - w[i]] + v[i]);
        else // 01 背包
            for(int j=W; j>=w[i]; j--)
                f[j] = max(f[j], f[j - w[i]] + v[i]);
    }

    cout << f[W];
    return 0;
}

二维费用背包

P1855 榨取kkksc03

0-1 背包问题。不同的是选一个物品会消耗两种价值（经费、时间），只需在状态中增加一维存放第二种价值即可。

#include<bits/stdc++.h>
using namespace std;

const int MAX = 200+5;
int t[MAX], m[MAX], f[MAX][MAX];

int main()
{
    int n, M, T;
    cin >> n >> M >> T;

    for(int i=1; i<=n; i++)
        cin >> m[i] >> t[i];

    for(int k=1; k<=n; k++)
        for(int i=M; i>=m[k]; i--)
            for(int j=T; j>=t[k]; j--)
                f[i][j] = max(f[i][j], f[i - m[k]][j - t[k]] + 1);

    cout << f[M][T];
    return 0;
}

分组背包

其实是从「在所有物品中选择一件」变成了「从当前组中选择一件」，于是就对每一组进行一次 0-1 背包就可以了。

如何进行存储。我们可以将 t_{k,i} 表示第 k 组的第 i 件物品的编号是多少，再用 \mathit{cnt}_k 表示第 k 组物品有多少个。

P1757 通天之分组背包

#include<bits/stdc++.h>
using namespace std;

const int MAX = 1e3+5;
int n, m, w[MAX], v[MAX], f[MAX], t[MAX][MAX], cnt[MAX], tMax=0;

int main()
{
    cin >> m >> n;
    for(int i=1; i<=n; i++)
    {
        int c; cin >> w[i] >> v[i] >> c;
        t[c][++cnt[c]] = i;
        tMax = max(tMax, c);
    }

    for (int k = 1; k <= tMax; k++) // 循环每一组
        for (int i = m; i >= 0; i--) // 循环背包容量
            for (int j = 1; j <= cnt[k]; j++) // 循环该组的每一个物品
                if (i >= w[t[k][j]]) // 背包容量充足
                    f[i] = max(f[i], f[i - w[t[k][j]]] + v[t[k][j]]); // 0-1背包

    cout << f[m];
    return 0;
}

有依赖背包

物品分为主件和附件两类，且每个主件最多包含两个附件，不妨枚举所有的主件。对于每次枚举，会有五种情况：

• 什么都不买
• 只买主件
• 买主件和第一个附件
• 买主件和第二个附件
• 买主件和两个附件

因为这几种可能性只能选一种，所以可以将这看成分组背包。

P1064 [NOIP 2006 提高组] 金明的预算方案

#include<bits/stdc++.h>
using namespace std;

const int MAX = 1e5+5;
int n, m, p[MAX], v[MAX], f[MAX], t[MAX][5], cnt[MAX], q[MAX];
int main()
{
    cin >> m >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> v[i] >> p[i] >> q[i];
        if(q[i] == 0) t[i][++cnt[i]] = i;
    }
    for(int i=1; i<=n; i++)
        if(q[i]) t[q[i]][++cnt[q[i]]] = i;

    for (int k = 1; k <= n; k++) // 循环每一组
        if(cnt[k] > 0 && t[k][1] == k)
            for (int i = m; i >= 0; i--) // 循环背包容量
            {
                if(cnt[k] >= 1)
                    if(i >= v[t[k][1]])
                        f[i] = max(f[i], f[i - v[t[k][1]]] + v[t[k][1]] * p[t[k][1]]);
                if(cnt[k] >= 2)
                    if(i >= v[t[k][1]] + v[t[k][2]])
                        f[i] = max(f[i], f[i - (v[t[k][1]] + v[t[k][2]])] + v[t[k][1]] * p[t[k][1]] + v[t[k][2]] * p[t[k][2]]);
                if(cnt[k] >= 3)
                    if(i >= v[t[k][1]] + v[t[k][3]])
                        f[i] = max(f[i], f[i - (v[t[k][1]] + v[t[k][3]])] + v[t[k][1]] * p[t[k][1]] + v[t[k][3]] * p[t[k][3]]);
                if(cnt[k] >= 3)
                    if(i >= v[t[k][1]] + v[t[k][2]] + v[t[k][3]])
                        f[i] = max(f[i], f[i - (v[t[k][1]] + v[t[k][2]] + v[t[k][3]])] + v[t[k][1]] * p[t[k][1]] + v[t[k][2]] * p[t[k][2]] + v[t[k][3]] * p[t[k][3]]);
            }

    cout << f[m];
    return 0;
}

树上背包

是树形DP和背包的结合。有依赖背包。

：我们发现背包的结果是可合并的。

经典树上背包：

P2014 [CTSC1997] 选课

• 状态：dp[u][i] 表示 u 子树中合法选了 i 门课的最大学分。
• 转移：dp[u][i+j] = \max(dp[u][i+j], dp[u][i] + dp[v][j])

  void dfs(int u)
  {
  dp[u][1] = val[u];
  siz[u] = 1;
  for(int v : edge[u])
  {
      dfs(v); // 得到 v 的背包
      for(int i=siz[u]; i>=1; i--) // 枚举 u 联通块的背包重量
          for(int j=siz[v]; j>=0; j--) // 枚举 v 联通块的背包重量
              dp[u][i+j] = max(dp[u][i+j], dp[u][i] + dp[v][j]);
      siz[u] += siz[v];
  }
  }

• 答案：dp[\text{root}][m]

状压 DP

【板】\text{AT\_abc318\_d [ABC318D] General Weighted Max Matching}

初始：$\text{all=0}$。

P1122 最大子树和

思路：

1. 【Trick】有根树上任意一个连通子图，在树中都有且只有唯一个“顶点”有根树上任意一个结点，都可以代表一部分以它为“顶点”的连通子图。

2. 状态：dp[u] 表示以 u 为“顶点”的连通子图中的最大点权和。

   转移：\text{dp[u]=val[u]+sum\{max\{0, dp[son]\}\}}

   初始：\text{all=0}

   答案：\text{max\{dp[i]\}}

P2016 战略游戏

1. 状态：dp[u] 表示 u 的子树最少需要放多少士兵才能瞭望所有边。

   转移：\text{dp[u]=sum\{dp[son]\}}

2. 【经验】发现上述转移部位判定父子边的瞭望关系，所以需要父子结点是否有士兵的信息，于是考虑升维：

   状态：dp[u][0/1] 表示 u 的子树，u 没有/有士兵的前提下，最少需要多少士兵能瞭望所有边。

   转移：\text{dp[u][0]=sum\{dp[son][1]\}}; \text{dp[u][1]=sum\{min\{dp[son][0], dp[son][1]\}\} + 1}.

   初始：\text{all=0}

   答案：\text{min\{dp[root][0], dp[root][1]\}}

区间 DP

在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。

令状态 f(i,j) 表示将下标位置 i 到 j 的所有元素合并能获得的价值的最大值，那么 f(i,j)=\max\{f(i,k)+f(k+1,j)+v\}，v 为将这两组元素合并起来的价值。

特点

合并：即将两个或多个部分进行整合，当然也可以反过来；

特征：能将问题分解为能两两合并的形式；

求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。

例: P1880 [NOI1995] 石子合并

令 f(i,j) 表示将区间 [i,j] 内的所有石子合并到一起的最大得分。