Acwing算法基础课第五讲总结

自来也sama 收录于类别 Acwing算法基础课

2021-04-02 2021-04-02 约 3251 字预计阅读 7 分钟

本讲主要内容

背包问题，线性DP，区间DP，计数类DP，数位统计DP，状态压缩DP，树形DP，记忆化搜索。

背包问题

AcWing-2 01背包问题

思路

所有物品数量都为1。
状态表示：
f[i,j]
集合：
在前i件物品中，选择总体积不超过j的物品的所有选择方案
属性：
集合中所有选择方案中，价值最大的方案的价值具体值
状态计算：
集合划分为：包含了第i件物品f[i-1,j-v[i]]+w[i]和不包含第i件物品f[i-1,j]
状态转移方程：
f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i])

参考代码

朴素做法：
复杂度为$O(n^2)$。

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 1010;
int v[maxn], w[maxn];
int f[maxn][maxn];

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

    for(int i = 1; i <= n; i++) //在前i个物品中选择
    {
        //枚举体积j时，由于f[i,0]都是0，所以从0和1开始枚举都是一样的
        for(int j = 0; j <= m; j++) //且总体积不超过j的情况下的所有取法
        {
            f[i][j] = f[i-1][j];    //先将状态转移再考虑能否装下第i个物品
            if(j - v[i] >= 0)   //能装下第i个物品，装下后总体积相应的要减小v[i]，同时总价值加上w[i]
                f[i][j] = max(f[i-1][j-v[i]] + w[i], f[i-1][j]);

        }
    }
    cout << f[n][m] << endl;

    return 0;
}

优化做法：
在代码上面做等价变形即可，变形之后一定要保证状态转移方程和原来是等价的。
首先注意到，由于第一维只使用到了i和i-1这两个下标，那么可以优化为滚动数组，即一维的两层数组交替使用
又，注意到在状态转移方程中f[i]更新用到的状态都只和f[i-1]有关，也就是只要保证i是依次枚举到n就可以覆盖到所有状态了，所以不需要存储i这一维
而由于在枚举j的时候，显然有能够放进背包的物品的总体积始终不会超过j，即v[i]<=j恒成立，v[i]的值只会在j的一侧。
那么直接用一维数组来存储总体积不超过j的物品的总价值即可
但需要注意的是，由于去掉i那一维之后，新的状态转移方程用到的都是当前的i这一维的状态，和原状态转移方程不等价
要使得新的代码和原来的状态转移方程等价的话，那么只有逆序枚举j 这样才能保证是用上一轮即i-1轮的状态来更新当前的状态
比如，更新f[7]时，用的就是第i-1轮时的f[4]的值，当前的f[4]（也就是第i轮）的值，会在更新完f[7]之后再算

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 1010;
int v[maxn], w[maxn];
int f[maxn];

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

    for(int i = 1; i <= n; i++) 
        for(int j = m; j >= v[i]; j--) 
            f[j] = max(f[j-v[i]] + w[i], f[j]);

    cout << f[m] << endl;

    return 0;
}

AcWing-3 完全背包问题

原题链接

思路

所有物品的数量为无限个。
状态表示：f[i][j]
集合：
在前i个物品中选择总体积不超过j的物品的所有选法
属性：
所有选法价值的最大值
状态计算：
集合划分为，第i个物品取了0~k个（k的范围是0到正无穷，但由于背包容积有限，所以k的值为有限值）。
状态转移方程：
f[i][j] = max(f[i-1][j-k * v[i]] + k * w[i])

参考代码

朴素做法：
这里由于每种物品有无限个，所以还需要多一重循环来枚举第i个物品取了多少个，复杂度为$O(n^3)$，从而朴素做法会超时。

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 1010;
int f[maxn][maxn];
int v[maxn], w[maxn];

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

    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
            for(int k = 0; k * v[i] <= j; k++)
                f[i][j] = max(f[i][j], f[i-1][j - k*v[i]] + k*w[i]);

    cout << f[n][m] << endl;

    return 0;
}

时间复杂度优化：
由状态转移方程f[i][j]和f[i][j-v[i]]展开并比较它们
可以得出简化后的等价状态转移方程f[i][j]=max(f[i-1][j], f[i][j-v[i]]+w[i])
从而可以去掉枚举每种物品取的个数k的那层循环，使得时间复杂度降至平方级别

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 1010;
int f[maxn][maxn];
int v[maxn], w[maxn];

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

    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }
    }
    cout << f[n][m] << endl;

    return 0;
}

空间复杂度优化：
类似于01背包的思路，但是注意两者的区别，这里的j可以不用逆序枚举
因为这里的状态转移方程中对应用到的就是第i轮的状态，而顺序枚举对应的就是用第i轮的状态去更新的

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 1010;
int f[maxn];
int v[maxn], w[maxn];

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

    for(int i = 1; i <= n; i++)
        for(int j = v[i]; j <= m; j++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}

AcWing-4 多重背包问题 I

原题链接

思路

每件物品的数量都有限且不同。
状态表示：
f[i][j] 集合：
前i个物品中选择总体积不超过j的所有选法。
属性：
所有选法价值最大值。
状态计算：
集合划分为，第i种物品取了0~s[i]件。
从而状态转移方程为f[i][j] = max(f[i-1][j - k*v[i]] + k*w[i]（注意k的取值范围和完全背包问题不同）。

参考代码

朴素做法：
复杂度为$O(n^3)$。

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 1010;
int f[maxn][maxn];
int v[maxn], w[maxn], s[maxn];

int main(void)
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];

    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
            for(int k = 0; k <= s[i] && k * v[i] <= j; k++)
                f[i][j] = max(f[i][j], f[i-1][j - k*v[i]] + k*w[i]);

    cout << f[n][m] << endl;

    return 0;
}

AcWing-5 多重背包问题 II

原题链接

思路

用二进制的思路来将多重背包问题转化成01背包问题
即用2的各幂次项来凑出s[i]。

参考代码

优化做法（时间复杂度为$O(n^2logs）$：

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 25000; //转化后的物品个数为N*logs
int f[maxn];
int v[maxn], w[maxn];

int main(void)
{
    int n, m;
    cin >> n >> m;
    int cnt = 0;    //存放转化后的物品个数
    for(int i = 1; i <= n; i++)
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while(k <= s)
        {
            cnt++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if(s >= 0)  //2的幂次项凑不了的部分
        {
            cnt++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    n = cnt;
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j-v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}

AcWing-9 分组背包问题

原题链接

思路

每组物品有若干个，同一组内的物品最多只能选一个。
状态表示：
f[i][j]
集合：
只从前i组物品当中选，且总体积不超过j的情况下的所有选法。
属性：
所有选法价值的最大值。
状态计算：
集合划分为，第i组物品中选了0个或选了第k个。
从而状态转移方程为：f[i][j] = max(f[i-1][j], f[i-1][j-v[i][k]] + w[i][k])

参考代码

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 110; //转化后的物品个数为N*logs
int f[maxn];
int v[maxn][maxn], w[maxn][maxn], s[maxn];

int main(void)
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> s[i];
        for(int j = 1; j <= s[i]; j++)
        {
            cin >> v[i][j] >> w[i][j];
        }
    }

    for(int i = 1; i <= n; i++)
        for(int j = m; j >= 0; j--) //注意这里要写成大于等于0
            for(int k = 1; k <= s[i]; k++)
                if(j >= v[i][k])
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

    cout << f[m] << endl;

    return 0;
}

线性DP

AcWing-898 数字三角形

原题链接

思路

状态表示：
f[i][j]
集合：
所有从起点走到点(i, j)的路径走法。
属性：
所有走法中，路径上的数字之和最大值。
状态计算：
集合划分为，走到(i, j)这个数的位置在左上和右上两种情况。
从而递推方程为， f[i][j] = max(f[i-1][j-1] + a[i][j], f[i-1][j] + a[i][j])。

参考代码

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 510;
const int inf = 2e9;
int f[maxn][maxn];
int a[maxn][maxn];

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

    //初始化的时候注意把数字三角形左右两边的空隙部分也初始化为负无穷
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= i + 1; j++)
            f[i][j] = -inf;

    f[1][1] = a[1][1];
    for(int i = 2; i <= n; i++)
        for(int j = 1; j <= i; j++)
            f[i][j] = max(f[i-1][j-1] + a[i][j], f[i-1][j] + a[i][j]);

    int res = -inf;
    for(int i = 1; i <= n; i++)  res = max(res, f[n][i]);

    cout << res << endl;

    return 0;
}

AcWing-

区间DP

计数类DP

数位统计DP

状态压缩DP

树形DP

记忆化搜索

AcWing-901 滑雪

原题链接

思路

记忆化搜索。有点像dfs，但是还是用了动态规划的思想，是动态规划的递归实现。
f[i][j]表示从点(i, j)出发的所有能走的路径，而它存储的就是从它出发的所有路径中最长的路径的长度。
递推方程为f[i][j] = f[i+dx][j+dy] + 1。
也就是将集合划分为从该点朝上下左右四个方向走下一步的四种路径，而状态计算的方式就是先得到去掉当前走到这一个点这一步，只看从下一个点出发走的路径的最大值，最后再加上走到这个点的路径长度1，那么最后得到的就是从点(i, j)走的所有路径长度的最大值。
这里是先用到的后面的状态，所以递归求解显得很方便。

参考代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 310;
int a[maxn][maxn];
int f[maxn][maxn];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
int r, c;

int dp(int x, int y)
{
    int &v = f[x][y];   //简化代码，记得加&

    if(v != -1) return v;   //走过的点不计入路径长度，直接结束这层递归

    v = 1;  //走到当前这个点，路径长度加1
    for(int i = 0; i < 4; i++)
    {
        int tx = x + dx[i], ty = y + dy[i];
        if(tx >= 1 && tx <= r && ty >= 1 && ty <= c && a[tx][ty] < a[x][y])
        {
            //递推方程的体现
            v = max(v, dp(tx, ty) + 1);
        }
    }

    return v;   //当前点周围已经没有能够继续滑下去的点，结束这层递归
}

int main(void)
{
    scanf("%d %d", &r, &c);
    for(int i = 1; i <= r; i++)
        for(int j = 1; j <= c; j++)
        scanf("%d", &a[i][j]);

    memset(f, -1, sizeof(f));   //标记是否达到过该点，并存储路径长度
    int res = 0;
    for(int i = 1; i <= r; i++)
        for(int j = 1; j <= c; j++)
            res = max(res, dp(i, j));

    printf("%d\n", res);

    return 0;
}

参考资料

AcWing-2 01背包问题参考资料1
AcWing-2 01背包问题参考资料2
AcWing-900 整数划分参考资料

目录

Acwing算法基础课第五讲总结

背包问题

AcWing-2 01背包问题

AcWing-3 完全背包问题

AcWing-4 多重背包问题 I

AcWing-5 多重背包问题 II

AcWing-9 分组背包问题

线性DP

AcWing-898 数字三角形

AcWing-

区间DP

计数类DP

数位统计DP

状态压缩DP

树形DP

记忆化搜索

AcWing-901 滑雪

参考资料