背包DP

套物品数量，花费，价值，背包容量

一.0/1背包

n个物品，每个物品价值wi，体积vi，背包容量为m，

每个物品可选可不选，求总体积不超过m的前提下，物品的最大价值

 f[i][j]:考虑前i个物品的情况下总体积为j的背包的最大价值

f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])

因为当前阶段只与上一阶段有关，所以省略掉第一维，倒序循环花费，保证每个物品只选择一次

f[j]=max(f[j],f[j-v[i]]+w[i])

二.完全背包

n种物品，每种物品有无限个

正序循环花费，同阶段的转移保证每个物品可以选择无限次

三.多重背包

n种物品，每种物品有ci个

二进制拆分多重背包

四.分组背包

n组物品，每组物品有ci个，第i组第j个物品的体积为Vi,j，

价值为Wi,j，每组物品至多选择一个（可以不选）

for(int i=1;i<=n;++i)
    //倒序循环：上一阶段转移过来 
    for(int j=m;j>=0;--j)
        for(int k=1;k<=c[i];++k){
            if(j-v[i][k]>=0)
                f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
        }

注意枚举顺序：阶段->状态->决策