闫式dp分析法

1.状态表示
(1).集合：当前f[i][j]表示的内容的集合
(2).属性：所取值在集合中的的属性，例如最大值或者最小值
2.递推公式
选或者不选分情况讨论

一 01背包问题

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])(第二重循环更改为从大到小)的原理是：
（1）观察第一个式子max里面的两个f第一维都是i-1，因为第一重循环是从小到大，所以当循环到i时，f的数据一定是在i-1的层次中，所以可以把第一维给优化掉；
（2）设v[i] < J< j，当更新f[i][J]的时候需要保证f[J]在i-1层次，如果第二重循环是从小到大，当在i层次更新到j时，比j小的J一定为更新为i层次中的值，所以需要将第二重循环变为从大到小保证更新到j的时候比j小的J没有被更新到i层次，还是i-1的层次

二. 完全背包问题

这里的物品可以选择0~k个，有k+1种选择，
递推公式为
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i],~,f[i-1][j-k[v[i]]]+Kw[i],·······);
又因为
f[i][j-v[i]]=max(f[i-1][j-v[i]],f[i-1][j-v[i]-v[i]]+w[i],~,f[i-1][j-v[i]-kv[i]]+kw[i])；(f[i-1][j-v[i]-kv[i]]+kw[i]),·······)这里的意义不是选了k+1个物品，而是从j-v[i]的体积中选择k个物品
所以
f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
因为f[i][j-v[i]]+w[i]是在i这个层次中，所以第二重循环是从小到大

三. 多重背包问题

(1).数据范围较少
三重从小到大的循环，最后一重循环枚举个数,相较于01背包仅仅增加了选择的个数

(2).数据范围大
二进制优化方达：

对于任意一个数，例如7，分解为 1 2 4，这几个数字加起来能组成1~7的任意一个数：对于11，分解为 1 2 4 4
如果x不是log的个数，那么需要的数字个数是log2(x)+1，否则需要的数字个数是log2(x)上取整。
对于x，只要循环计算x-1-2-4-8-···-2^n=y (y<2^n+1) 减到不为负数为止的所有数然后加上最后余的数就是二进制分解后的数.实现如下

    for(int j=1;j<=n;j++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        for(int i=1;c>=i;i*=2)
        {
                c-=i;
                v[cnt]=i*a;
                w[cnt++]=i*b;
        }
        if(c)
        {
            v[cnt]=c*a;
            w[cnt++]=c*b;
        }
    }

综上，只需要把物品按上述方法分解就能转化为01背包问题

四. 分组背包

三重循环，依次枚举组别，体积，物品 。这里为什么先枚举组别呢，在这里的组别相当于01背包的物品
它相对于01背包问题就在于物品有k+1中选择，01背包有2种选择，只要在多一重循环枚举这k个物品，就能转化为01背包问题
最后它和01背包的第二重循环完全一样需要从大到小枚举
分组背包的存储方式与前几种背包问题不同，需要二维数组存储第几组的第几个物品