本文最后更新于：3 个月前

从集合角度分析DP问题

算法特点

一般问法：最值（价值等属性）、达到某一目标的方向总数
背包问题的本质为组合问题，即在一定条件下从一部分物品中挑选物品；同时也类似于图论的最短路，可以说，DP是一种特殊的图论
暴力做法：方案数量为指数级
化零为整：挖掘不同方案间的共同关系，把有相同关系的元素放在一起
化整为零：把一个集合划分为多个子集，进行分析
解决问题的过程中一定抓住从实际含义出发

具体的分析在下述例题中会有解释

题解的优化可以参考ACDaily 4

01背包

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

本题题解具体优化可以参考ACDaily 4，此处借此例讲解动态规划基本的算法架构

算法架构：动态规划集合化

状态表示（一般为二维，不可能超时）f[i][j]
- 集合的思想，f[i][j]表示的并非是j体积背包下对前i个物品进行选择下的价值最大值，而是j体积下对前i个物品进行选择下的所有方案的最大价值（每个物品可选可不选）
- 属性：min、max、count，即数组中的元素表示最值或方案数
状态计算(化零为整)
1. 集合的划分，划分依据：最后一个不同点。即在限制条件下（确定问题域），按选或不选第i个物品（i个物品中的最后物品）对方案进行划分为A（选i）和B（不选i)集合
  - 要求：不重不漏，每个子集中的元素具有相同共性（都选或没选第i个物品），各子集又能组合成全集
2. 对不选i的集合中（B）所有方案的最大价值进行计算，得到max1
3. 按物品选择是否发生变化，对上述划分包含选择第i个物品的方案（即A方案集合）进行分区，物品i所在区域为不变区，前i-1个物品组成的区域为变化区
4. 寻找变化区中总价值最大的物品选择方案，加上第i个物品的价值，得到最大价值max2
5. 求max(max1, max2),得到整体最大价值
关键在于选择划分方式，例如以下的摘花生与最大子序列长度

1. 摘花生

Hello Kitty想摘点花生送给她喜欢的米老鼠。

她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。

地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty只能向东或向南走，不能向西或向北走。

问Hello Kitty最多能够摘到多少颗花生。

输入格式

第一行是一个整数T，代表一共有多少组数据。

接下来是T组数据。

每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。

每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。

输出格式

对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。

数据范围

1≤T≤100,
1≤R,C≤100,
0≤M≤1000

输入样例：

2
2 2
1 1
3 4
2 3
2 3 4
1 6 5

输出样例：

8
16

题解：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 55, MOD = 1000000007;
int w[N][N];
int f[N][N][13][14];

int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {    
            cin >> w[i][j];
            w[i][j]++;  // 调整整体价值范围
        }
            
    f[1][1][0][0] = 1;
    f[1][1][1][w[1][1]] = 1;  // 初始化
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            if(i == 1 && j == 1) continue;  // 起点已进行过初始化
            for(int u = 0; u <= k; u++)
                for(int v = 0; v <= 13; v++)
                {
                    int &val = f[i][j][u][v];
                    val = (val + f[i-1][j][u][v]) % MOD;
                    val = (val + f[i][j-1][u][v]) % MOD;
                    
                    if(u > 0 && v == w[i][j])
                    {
                        for(int c = 0; c < v; c++)
                        {
                            val = (val + f[i-1][j][u-1][c]) % MOD;
                            val = (val + f[i][j-1][u-1][c]) % MOD;
                        }
                        
                    }
                }
        }
    
    int res = 0;    
    for(int c = 0; c <= 13; c++) res = (res + f[n][m][k][c]) % MOD;
    
    cout << res << endl;
    return 0;
}

2. 最长上升子序列

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 N。

第二行包含 N 个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N≤1000，
−109≤数列中的数≤109

输入样例：

7
3 1 2 1 8 5 6

输出样例：

题解：

#include <iostream>

using namespace std;

const int N = 1010;

int n;
int w[N], f[N];

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

    int mx = 1;    // 找出所计算的f[i]之中的最大值，边算边找
    for (int i = n; i >= 0; i--) {
        f[i] = 1;    // 设f[i]默认为1，找不到前面数字小于自己的时候就为1
        for (int j = i+1; j < n; j++) {
            if (w[i] < w[j]) f[i] = max(f[i], f[j] + 1);    // 这种写法是f[j]已经更新过的正常写法
        }
        mx = max(mx, f[i]);
    }

    cout << mx << endl;
    return 0;
}

3. 地宫寻宝

X 国王有一个地宫宝库，是 n×m 个格子的矩阵，每个格子放一件宝贝，每个宝贝贴着价值标签。

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。

当小明走到出口时，如果他手中的宝贝恰好是 k 件，则这些宝贝就可以送给小明。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 k 件宝贝。

输入格式

第一行 3 个整数，n,m,k，含义见题目描述。

接下来 n 行，每行有 m 个整数 Ci 用来描述宝库矩阵每个格子的宝贝价值。

输出格式

输出一个整数，表示正好取 k 个宝贝的行动方案数。

该数字可能很大，输出它对 1000000007 取模的结果。

数据范围

1≤n,m≤50,
1≤k≤12,
0≤Ci≤12

输入样例1：

2 2 2
1 2
2 1

输出样例1：

输入样例2：

2 3 2
1 2 3
2 1 5

输出样例2：

题解：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 55, MOD = 1000000007;
int w[N][N];
int f[N][N][13][14];

int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {    
            cin >> w[i][j];
            w[i][j]++;  // 调整整体价值范围
        }
            
    f[1][1][0][0] = 1;
    f[1][1][1][w[1][1]] = 1;  // 初始化
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            if(i == 1 && j == 1) continue;  // 起点已进行过初始化
            for(int u = 0; u <= k; u++)
                for(int v = 0; v <= 13; v++)
                {
                    int &val = f[i][j][u][v];
                    val = (val + f[i-1][j][u][v]) % MOD;
                    val = (val + f[i][j-1][u][v]) % MOD;
                    
                    if(u > 0 && v == w[i][j])
                    {
                        for(int c = 0; c < v; c++)
                        {
                            val = (val + f[i-1][j][u-1][c]) % MOD;
                            val = (val + f[i][j-1][u-1][c]) % MOD;
                        }
                        
                    }
                }
        }
    
    int res = 0;    
    for(int c = 0; c <= 13; c++) res = (res + f[n][m][k][c]) % MOD;
    
    cout << res << endl;
    return 0;
}

ACDaily

DP 背包问题

本文作者: waitingFor
本文链接: http://example.com/2022/03/05/ACDaily/ACDaily-5/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

ACDaily 6 上一篇

ACDaily 4 下一篇

ACDaily 5

从集合角度分析DP问题

算法特点

01背包

算法架构：动态规划集合化

1. 摘花生

输入格式

输出格式

数据范围

输入样例：

输出样例：

题解：

2. 最长上升子序列

输入格式

输出格式

数据范围

输入样例：

输出样例：

题解：

3. 地宫寻宝

输入格式

输出格式

数据范围

输入样例1：

输出样例1：

输入样例2：

输出样例2：

题解：