三、多重背包
与完全背包不同的是每一个物品的数目不是无限的，而是以s[i]来记录
状态表示：仍然以f[i][j]来表示选取前i个物品，且背包容量为j的所有选法、
状态计算：在朴素的情况下还是和完全背包相差无几
f[i][j]=max(f[i-1][j-kv[i]]+kw[i]) (k=0,1,2……s[i])
于是可以得到朴素版本的代码：

#include<iostream>
#include<algorithm>
using namespace std;

const int N=110;

int n,m;
int v[N],w[N],s[N];
int f[N][N]; 

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int k=0;k<=s[i]&&k*v[i]<=j;k++){
                f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
} 

思考其优化方案，同样联想数列的递推公式，不同于完全背包的一点是，由于多重背包是受数量限制的，所以相减的最后一项无法被约去（完全背包被约去可以考虑成极限的情况）,因为多了这最后一项，所以不再按照完全背包的优化方案来优化。

倍增思想之二进制优化（真就万物皆可二进制）

若s=1023
将第i个物品分组，分为(1,2,4,8……,512)共十组,且每一组只选一次，因为任何一个数都可以表示成二进制，所以在每组只选一次的情况下能够表示出0~1023之间的所有数
若s是一个普通的数，只需要在最后一组补上差值，使得所有的分组值能够表示出0~s以内的所有数，最终也就转换成了01背包问题
代码如下，注意如何分组即可

#include<iostream>
#include<algorithm>
using namespace std;

const int N=12010,M=2010;

int n,m;
int v[N],w[N];
int f[M];

int main(){
    cin>>n>>m;
    //step1:分组 
    int cnt=0;//组序号 
    for(int i=1;i<=n;i++){
        int a,b,s;
        cin>>a>>b>>s;//v,w,s
        int k=1;
        while(k<=s){
            cnt++;
            v[cnt]=a*k;//打包后该组的总体积
            w[cnt]=b*k;//打包后该组的总价值 
            s-=k;
            k*=2;  
        }
        if(s>0){
            cnt++;//剩下的成为一组
            v[cnt]=a*s;
            w[cnt]=b*s;
        } 
    } 
    n=cnt;//更新组数
    //选或不选，又回到01背包
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    } 
    cout<<f[m]<<endl;
    return 0;
}

四、分组背包
有多组物品，且同一组的物品最多只能选一个（可以不选）
1.
状态表示之集合：只从前i组物品中选，且总体积不大于j的所有选法
状态表示之属性：Max Value
2.状态计算（实际上是一个集合划分的过程）
和完全背包不同，完全背包的划分是对于第i组物品要选几个，以选择的个数来作为划分依据；而分组背包的划分是对于第i组物品，要选哪一个，以选择的对象来作为划分的依据。

朴素算法的代码如下，依次枚举物品、体积和决策（第i个物品,背包还能放的体积，要放第i组的第k个物品，k是多少？）

#include<iostream>
#include<algorithm>
using namespace std;

const int N=110;
int n,m;
int v[N][N],w[N][N],s[N];
int f[N][N];

int main(){
    //输入
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=1;j<=s[i];j++){
            cin>>v[i][j]>>w[i][j];
        }
    }
    //枚举
    for(int i=1;i<=n;i++){//物品组别
        for(int j=1;j<=m;j++){//容量
            for(int k=0;k<=s[i];k++){//决策组内编号
               if(j>=v[i][k]) f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
            }

        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

可以看出分组背包的朴素算法和多重背包的朴素算法，二者的区别就在于状态转移方程。

由于分组背包中的组中每一个物品都是不一样的，这难以组合或者分类（无法用二进制或单调队列来进行优化），时间复杂度很难再优化，但是在空间复杂度上，仍然可以降维处理，因为状态转移只取决于上一行。
从上面的朴素算法也可以看出，f[i][j]的更新利用的是f[i-1][……],也就是说利用的是旧值，在优化时需要逆序处理j,代码如下：

#include<iostream>
#include<algorithm>
using namespace std;

const int N=110;

int n,m;
int v[N][N],w[N][N],s[N];
int f[N];

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=1;j<=s[i];j++){
            cin>>v[i][j]>>w[i][j];
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=m;j>=1;j--){ 
            for(int k=0;k<=s[i];k++){
                if(j>=v[i][k]) 
                f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
            }

        }
    }
    cout<<f[m]<<endl;
}

如果采用计时输入，那么v和w也可以降维

#include<iostream>
#include<algorithm>
using namespace std;

const int N=110;

int n,m,s;
int v[N],w[N];
int f[N];

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){//物品组别 
        cin>>s;
        for(int i=1;i<=s;i++) cin>>v[i]>>w[i];//读入组内物品的体积情况 
        for(int j=m;j>=1;j--){//体积 
            for(int k=0;k<=s;k++)
                if(j>=v[k]) f[j]=max(f[j],f[j-v[k]]+w[k]); 
        }
    }

    cout<<f[m]<<endl;
}

思考:体积和决策的顺序能否颠倒呢？

答案是否定的，理由如下，如果先决策的话，就会更新与当前体积不同的其他体积所对应的价值，这会使得f[j-v[k]]!=f[i-1][j-v[k]]