多重背包

1019. 庆功会

思路： 多重背包，体积很小，物品数量也很小，可以直接枚举物品的数量。

#include<bits/stdc++.h>
using namespace std;
const int N=6000;
int dp[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1,v,w,s;i<=n;++i){
        cin>>v>>w>>s;
        for(int j=m;j>=v;--j){
            for(int k=0;k<=s&&k*v<=j;++k){
                dp[j]=max(dp[j-k*v]+w*k,dp[j]);
            }
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}

7. 混合背包问题

思路： 物品数量和体积各1000，物品数量也是1000，暴力个数的肯定不行，可以将物品的个数按二进制拆分。

#include<bits/stdc++.h>
using namespace std;
const int N=1010 ;
int dp[N];
int main(){
    int n,m;
    cin>>n>>m;
    while(n--){
        int v,w,s;
        cin>>v>>w>>s;
        if(w<0) continue;
        if(s==-1){
            for(int i=m;i-v>=0;--i)
                dp[i]=max(dp[i-v]+w,dp[i]);
        }
        else if(s==0){
            for(int i=v;i<=m;++i)
                dp[i]=max(dp[i-v]+w,dp[i]);
        }
        else {
            int tmp=1;
            while(s){
                if(s>=tmp)
                    s-=tmp;
                else tmp=s,s=0;
                int tv=tmp*v;
                int tw=tmp*w;
                for(int i=m;i>=tv;--i){
                    dp[i]=max(dp[i],dp[i-tv]+tw);
                }
                tmp*=2;
            }
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}

6. 多重背包问题 III

男人八题！
思路：

注意画图的两个方向不同，上面是左到右体积减小，下面相反。
需要滑动窗口的思想。
第一步：我们需要枚举余数r，即体积为r+t*v(0<=t<=s)，由递推式可以看出来单调队列优化的背包和完全背包一样需要从小到大枚举体积，对于当前体积越往大枚举，整体偏移量大一个w；在同一个窗口下，体积越小偏移量越大。可以发现的窗口头的体积减去窗口中的值就是准确的偏移值。

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=20010;
int f[N],t[N],q[N];
int main(){
    int n,V;
    cin>>n>>V;
    for(int i=1,v,w,s;i<=n;++i){
        cin>>v>>w>>s;
        memcpy(t,f,sizeof f);
        for(int j=0;j<v;++j){
            int hh=0,tt=-1;
            for(int k=j;k<=V;k+=v){
                if(hh<=tt&&(k-q[hh])/v>s) hh++; //保证窗口的大小
                while(hh<=tt&& (t[q[tt]]+(k-q[tt])/v*w<=t[k]) ) tt--;//偏移量为到当前窗口头的距离
                q[++tt]=k;
                f[k]=t[q[hh]]+(k-q[hh])/v*w;//偏移量为到当前窗口头的距离
            }
        }
    }
    cout<<f[V];
}