Miku

多重背包板子

纯多重背包好想>$dp[i]=max{dp[i-kw[j]]+kv[j]}$

但是要优化。这里采用二进制优化。

二进制优化是啥呢，假如i物品有13个

13可以拆成1+2+4+6，然后用这四个，就可以表示除1-13所有可能了

这样就把多重背包优化成了01背包

#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int w[100001];
int v[100001];
int dp[100001];
int x,y,z;
int cnt;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d%d%d",&x,&y,&z);
        for(int j=1;j<=z;j=j<<1){
            cnt++;
            w[cnt]=y*j;
            v[cnt]=x*j;
            z-=j;
        }
        if(z){
            cnt++;
            w[cnt]=z*y;
            v[cnt]=z*x;
        }
    }
    for(int i=1;i<=cnt;++i){
        for(int j=m;j>=w[i];--j){
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    cout<<dp[m];
    return 0;
}

---------------、
再来个单调队列的

单调队列不好理解，最麻烦的事状态转移方程的转化

原来是$fj=max{f{j-kv} +kw}$

把j换成aw+d则
$fj=max{f{aw+d-kv} +kw}$

然后再改变一下$fj=max{f{aw+d-kv} +kw-aw}+aw$
就是$fj=max{f{（a-k)v+d} -(a-k)w}+aw$

哇哦，a-k出现了两边，并且如果我们按照%v的余数来分组。a-k就是在新分的组中的编号

然后就可以用单调队列解决了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int m,n,ans;
deque <int> q,q2;
int dp[40010];
int w,v,c,k;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){

//      cout<<endl;
        scanf("%d%d%d",&w,&v,&c);
        if(v==0){//单调队列专属特判 
            ans+=w*c;
            continue;
        }
        k=m/v;
        c=min(c,k);//能放的最多的 
        for(int j=0;j<v;++j){//按照余数处理 
            while(!q.empty()){//先清空 
                q.pop_back();
                q2.pop_back();
            }
            k=(m-j)/v;//能放多少呢 
            for(int z=0;z<=k;++z){
                while(!q.empty()&&dp[j+z*v]-z*w>=q2.back()){//单调队列 部分 
                //原来的此处极有可能是由上一个物品转移的
                //所以说-z*w，即是减去当前放的当前物品进行比较
                //因为最后还是要加的，就像下面 
                    q2.pop_back();
                    q.pop_back();
                }
                q.push_back(z);
                q2.push_back(dp[j+z*v]-z*w);//可转移 
                while(!q.empty()&&q.front()<z-c){//处理对头 
                    q2.pop_front();
                    q.pop_front();
                }
                dp[j+z*v]=max(dp[j+z*v],q2.front()+z*w);
            }
        }
    }
    cout<<ans+dp[m];
    return 0;
}