多重背包

题目类型：有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
朴素算法：
将所有物品都转换成只有一个物品，那么物品总数就是
n[1]+n[2]+...n[n]个，然后进行01背包

 for(int i=1;i<=k;i++)
 {
     for(int j=m;j>=v[i];j--)//逆序
     {
        for(int h=0;h<=cnt[i];h++)
        {
            if(j-h*v[i]<0)break;
            f[j]=max(f[j],f[j-h*pri[i]]+h*w[i]);
        }
     }
}
printf("%d\n",f[m]);

单调队列优化算法

int n=read(),m=read();//n是容量 
rep(i,1,m)
{
    memcpy(g,dp,sizeof(dp));//保存dp的副本 
    int v=read(),w=read(),num=read();//体积，价值，数量 
    for(int j=0;j<v;j++)//余数拆分成v个类
    {
        int now=0,back=-1;
        for(int k=j;k<=n;k+=v)//对每个类进行单调队列
        {
            if(now<=back&&q[now]<k-num*v) now++;//q[h]不在窗口[k-num*v,k-v]内，对头出队
            if(now<=back) dp[k]=max(g[k],g[q[now]]+(k-q[now])/v*w);//使用队头最大值更新
            while(now<=back && g[k]>=g[q[back]]+(k-q[back])/v*w) back--;//当前值比队尾值更有价值，队尾出队
            q[++back]=k; 
        }
    }
}
    printf("%d\n",dp[n]);