题解：P11297 [NOISG2018 Prelim] Knapsack

· · 题解

题意简单，就是一个多重背包。

但是这题的数据范围实在是反常。

我们发现这题的容量出奇的小，可以接受 S^2 左右的算法，带个 \log 也不算困难。

多重背包的标准复杂度最优是 nS 也就是单调队列优化，如果信仰足够强大也许能过，但是这个时间限制我觉得有点紧张，我们不妨考虑更优秀的做法。

首先看向这个 k_i，我们会发现这个 k 的数据范围只是吓人用的，就算每个物品重量都只有 1，我们也拿不到 10^9 个数，这是不可能的，最多只能拿 \lfloor\frac{S}{w} \rfloor 个，后面除法默认取整省去不写。

还没完，如果我们只看同种重量的物品，我们也只需要观察价值前 \frac{S}{w} 个，再往后显然是没有意义的。可以注意到重量的数量和 S 是一致的，分析时我们就认为重量正好是 S 种来分析复杂度。

简单分析一下现在物品数量的上界，是 \sum_{w=1}^n \frac{S}{w}，这是一个调和级数，大概约等于 S\log S。

我们直接对这些剩下的物品做简单的 01 背包，复杂度 O(S^2\log S+n\log n)，后面那个 n\log n 来自于排序。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
const int SN=2005;
int n,S;

struct node{
    int v,w,k;
    bool operator<(node x){
        return v<x.v;
    }
}a[N];
struct nd{
    int v,w;
}it[SN*30];
vector<node> item[SN];
int cnt;
int f[SN];
signed main(){
    cin>>S>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].v>>a[i].w>>a[i].k;
        item[a[i].w].push_back(a[i]);
    }
    for(int i=1;i<=S;i++) sort(item[i].begin(),item[i].end());
    for(int i=1;i<=S;i++){
        int j=0;
        while(j<=S/i and !item[i].empty()){
            it[++cnt]={item[i].back().v,item[i].back().w};
            j++;
            item[i].back().k--;
            if(!item[i].back().k) item[i].pop_back();
        }
    }
    for(int i=1;i<=cnt;i++){
        for(int j=S;j>=it[i].w;j--){
            f[j]=max(f[j],f[j-it[i].w]+it[i].v);
        }
    }
    cout<<f[S];
}