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

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

题目描述

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 ≤ 107,但实际测试数据中m×t似乎达到了109甚至1010,所以我们的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写的文章,相信大家看了之后一定会茅塞顿开:

好了,这篇文章就到这里了,谢谢!

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

返回顶部
京ICP备15050995号