P1776 宝物筛选

题目描述

终于，破解了千年的难题。小 FF 找到了王室的宝物室，里面堆满了无数价值连城的宝物。

这下小 FF 可发财了，嘎嘎。但是这里的宝物实在是太多了，小 FF 的采集车似乎装不下那么多宝物。看来小 FF 只能含泪舍弃其中的一部分宝物了。

小 FF 对洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：小 FF 有一个最大载重为 $W$ 的采集车，洞穴里总共有 $n$ 种宝物，每种宝物的价值为 $v_i$，重量为 $w_i$，每种宝物有 $m_i$ 件。小 FF 希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。

输入格式

第一行为一个整数 $n$ 和 $W$，分别表示宝物种数和采集车的最大载重。

接下来 $n$ 行每行三个整数 $v_i,w_i,m_i$。

输出格式

输出仅一个整数，表示在采集车不超载的情况下收集的宝物的最大价值。

说明/提示

对于 $30\mathrm{\%}$ 的数据，$n\le \sum m_i\le {10}^4$，$0\le W\le {10}^3$。

对于 $100\mathrm{\%}$ 的数据，$n\le \sum m_i\le {10}^5$，$0\le W\le 4\times {10}^4$，$1\le n\le 100$。

思路

多重背包模板问题,采用单调队列来优化

单调队列

洛谷日报讲的很清楚

状态转移：

f[i][j]=max(f[i−1][k′∗d+b]−k′∗w[i])+a∗w[i]

k'是没选中的,(a−k)=k'

题解

#include <iostream>
#include <cstring>
#include <deque>
#include <fstream>
#define debug(x) #x << ":" << x << " "
#define ll long long
using namespace std;

struct
{
    int v, w, m; // 价值,重量,数量
} goods[128];

int dp[2][40960]; // 使用滚动数组
int now = 0;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // fstream in;
    // in.open("in.txt", ios::in);
    // cin.rdbuf(in.rdbuf());
    memset(dp, 0, sizeof(dp));
    int n, W;
    cin >> n >> W;
    for (int i = 1; i <= n; i++)
    {
        cin >> goods[i].v >> goods[i].w >> goods[i].m;
    }

    for (int i = 1; i <= n; i++)
    {
        int pre = now;
        now = 1 - now;

        // 物品循环
        // 以余数分组
        // f[i][j]=max(f[i−1][k′∗d+b]−k′∗w[i])+a∗w[i]
        // j = a * w + b
        // k' = a - k
        // 注意j和k'是正相关的
        // int a = W / min(W / goods[i].w, goods[i].m); // 最大能选的数目

        for (int b = 0; b < goods[i].w; b++)
        {

            deque<int> que;
            // dp[now][b] = dp[]
            // 物品件数循环
            //
            for (int k = 0; k <= W / goods[i].w; k++)
            {
                // 加上k*w[i]的原因:
                // 我们的单调队列维护的是前i-1种的状态最大值.
                // 因此这里加上k*w[i].
                // k和b的组合其实就是j
                int j = k * goods[i].w + b;
                int now_v = dp[pre][j] - k * goods[i].v;

                while (!que.empty() && k - que.front() > goods[i].m)
                {
                    que.pop_front();
                }
                while (!que.empty() && dp[pre][que.back() * goods[i].w + b] - que.back() * goods[i].v <= now_v)
                {
                    que.pop_back();
                }
                que.push_back(k);

                // if (i == 2)
                // {
                //     cout << debug(que.front() * goods[i].w + b) << debug(que.front()) << " ";
                //     cout << debug(que.size()) << debug(k);
                //     cout << debug(dp[pre][que.front() * goods[i].w + b]) << "\n";
                //     // cout << debug(k - que.front()) <<" ";
                // }
                // 插入到单调队列, 注意, 单调队列中存的是位序, 这里存的是k
                dp[now][j] = dp[pre][que.front() * goods[i].w + b] + (k - que.front()) * goods[i].v;
            }
        }
        // for (int p = 0; p <= W; p++)
        // {
        //     cout << dp[now][p] << " ";
        // }
        // cout << "\n";
    }

    cout << dp[now][W];

    return 0;
}