题解：P11297 [NOISG2018 Prelim] Knapsack

· · 题解

前置芝士：多重背包的二进制优化或单调队列优化

双倍经验：

https://www.luogu.com.cn/problem/P1776

Solution：

思路：

首先我们看题意，仔细思考可以看出这是个多重背包 DP ，因为每个物品有多个，所以我们可以考虑多重背包的二进制优化，(其实单调队列的优化也可以，但是相比二进制优化比较难理解而且不是很好写)，想要学习单调队列优化的同学可以去上面双倍经验的题解学习一下。

优化讲解：

什么是二进制优化呢？我们可以举个例子。以 15 为例， 18=1+2+4+8+3 ，即 18=1_{2}+10_{2}+100_{2}+1000_{2}+3_{10} ，按照这样的二进制拆分后，我们可以用前四个二进制数分别表示 [1,15] 的数，至于 (15,18] 的数我们可以用已经表示的数加上3求得，因此我们可以通过枚举二进制拆分出来的方案得出每一个物品取 [0,k_{i}] 的情况，从而达到优化时间复杂度的目的。优化后的时间复杂度大概是 O(sn\sum_{i=1}^{n}k_{i}) 。

优化后结合背包板子即可，不想挂分的话记得数组开大一点

Codes：

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<cstdio>
#include<set>
#include<bitset>
#include<iomanip>
using namespace std;
int s,n;
const int N=1e7+5;
long long v[N],w[N],k[N],dp[N];
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>s>>n;
    long long a,b,c,cnt=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b>>c;
        long long k=1;
        while(k<=c)
        {
            v[++cnt]=k*a,w[cnt]=k*b;
            c-=k;
            k*=2;
        }
        if(c)
        {
            v[++cnt]=a*c,w[cnt]=b*c;
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=s;j>=w[i];j--)
        {
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    cout<<dp[s];
    return 0;
}