洛谷刷题记——P1616 疯狂的采药

最近在刷一些动规类型的题，这种算法对我来说是一个难啃的硬骨头，因为我并不是不懂动规的原理，而只是找不到动态转移方程，不过多刷刷题也能解决了。

文章目录

1 题目描述
2 知识链接
- 2.1 完全背包问题
- 2.2 滚动DP
3 解题思路
4 代码展示
5 写在最后

题目描述

见P1616 疯狂的采药 – 洛谷。

知识链接

完全背包问题

完全背包问题就是一种类似于0/1背包问题的变体（如果不知道0/1背包问题~~为什么不问问神奇海螺呢~~），只不过物体的个数是无限的！

设dp为记录动规路径的数组，w为物体的质量，v为物体的价值，则背包问题的动态转移方程为：

dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j])

我想以后可能不会再做这些模板题了，所以这里就先讲讲0/1背包吧。dp[i][j]记录的是“总容量为j，装i个物品的情况下，最大的价值是多少”，而题目要求的是“总容量为m，装n个物品的情况下，最大的价值是多少”，所以最后输出的结果显然就是dp[n][m]。至于如何求出这个dp[i][j]，这就涉及到了动规的精髓：状态转移。

dp[i][j]比dp[i][j – 1]多一份质量的总容量，这时我们有两种选择：装一个物品，或是啥都不装。如果装了这个物品，显然就需要给它腾出位置来，这就是前面的dp[i – 1][j – w[i]]，然后我们白白腾出了位置，怎能不获得价值呢？所以如果装了这个物品，dp[i][j] = dp[i – 1][j – w[i]] + v[i]。如果不装这个物品，dp[i][j]就还等于上一个状态，也就是dp[i][j] = dp[i][j – 1]。我们要求最大值，就要从这两种状态中挑出最大的来，也就是最终的状态转移方程：dp[i][j] = max(dp[i – 1][j – w[i]] + v[i], dp[i – 1][j])。

注意：完全背包问题的转移方程与之不同，为：dp[i][j] = max(dp[i][j – w[i]] + v[i], dp[i][j])，因为完全背包问题是同行比较。

这里我们要解决两个问题：一个是初始状态从哪里来呢？这个不难理解，你说动规是状态的转移，但如果没有最初的状态，你从哪转移啊？很简单，只要自己手动做一个初始状态就好了。装0个物品和总容量为0的状态都是装不了东西的，也就是0价值，只要建立一个循环，把dp[0][i]和dp[j][0]都初始化为0就行了，或者直接把数组整个初始化为0也行。

第二个问题：如果我选择装这个物体，但这个物体的质量比我当前背包的总容量还大，那我这么一减不就出来负数，出错了吗？这个也很简单，只要加一个特判就行了：

j < w[i] ? dp[i][j] = dp[i][j - 1] : dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]);

这样一来，当这个物品质量大于当前背包总容量时，就什么都不装，我们得出了最终的答案。

滚动DP

刚才我们已经把背包问题如何用DP解决讲得很清楚了，但刚才我们用的是二维数组，很是浪费空间。其实仔细分析后不难发现，每次动态转移我们只用到了当前物品的状态，可以通过这一点来把dp数组压缩到一维。

if (w[i] < j + 1)
{
    dp[j] = max(dp[j - w[i]] + v[i], dp[j]);
}

使用滚动DP不仅可以省下很多的空间，还可以在一定意义上节省时间（减少了内层的j循环）。

不过我们要注意的是：我们在解决0/1背包问题的时候，第二层的j循环一定是要倒着来的。这点网上也说的很清楚，因为如果不倒着来，会出现重复拿取物品的错误，这就不符合0/1背包了，因为每个物体只能拿一遍。而完全背包问题每个物体可以拿无限遍，所以内层的j循环要正着来。

解题思路

P1048是0/1背包问题的模板题，而这道题是完全背包问题的模板题，可以直接套用状态转移方程。不过这道题的数据较大~~（duliu出题人）~~，使用二维DP会超空间，我们选择滚动DP。

另外还有一点：本题数据描述有一条1 ≤ m×t ≤ 10⁷，但实际测试数据中m×t似乎达到了10⁹甚至10¹⁰，所以我们的dp数组一定要开long long而不是int，否则会炸掉~~（duliu出题人石锤）~~。~~当初洛谷还因为这个错误而撤掉30篇题解~~

代码展示

拒绝抄袭，共创和谐社会[机智]

#include <algorithm> // std::max
#include <array> // std::array
#include <cstdio> // std::printf, std::scanf

using namespace std;

array<array<int, 5>, 10005> _herbs; // 草药数组，存储草药的价值和质量，w数组和v数组的结合
array<long long, 10000005> _dp; // 动规数组，一定要开long long

int main(void)
{
    int m = 0, t = 0;

    _dp.fill(0); // 初始化动规数组

    for (array<array<int, 5>, 10005>::iterator iter = _herbs.begin(); iter != _herbs.end(); iter++) // 初始化草药数组
    {
        iter->fill(0);
    }

    scanf("%d %d", &t, &m);

    for (int i = 1; i < m + 1; i++)
    {
        scanf("%d %d", &_herbs[i][0], &_herbs[i][1]); // _herbs[i][0]存储草药的质量（采摘时间），_herbs[i][1]存储草药的价值
    }

    for (int i = 1; i < m + 1; i++)
    {
        for (int j = _herbs[i][0]; j < t + 1; j++) // 注意内层j循环一定要顺序循环
        {
            _dp[j] = max(_dp[j], _dp[j - _herbs[i][0]] + _herbs[i][1]); // 动态转移
        }
    }

    printf("%lld\n", _dp[t]); // dp数组开long long后，printf占位符也要相应改为%lld

    return 0;
}

写在最后

这是一道相对简单的完全背包问题的模板题，不过也有一些小坑~~（包括duliu出题人出的duliu数据）~~，注意一下就OK了。

不过关于上面的“知识链接”，真是应了一句古话：会做的不一定会讲~~（似乎没有这句古话）~~。我可能讲的不是很清楚，读者们听的肯定很迷糊。我在这里推荐几篇dalao写的文章，相信大家看了之后一定会茅厕塞顿开：

https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/dong-tai-gui-hua-xiang-jie-jin-jie（讲动规本身的）
https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/bei-bao-wen-ti（讲0/1背包的）
https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/bei-bao-ling-qian（讲完全背包的）
（以上三篇博文皆为一位dalao所写，使用的OJ网站为LeetCode，与本文使用的洛谷不同）
（看了还觉得迷糊的可以自行度娘）

好了，这篇文章就到这里了，谢谢！