闫氏DP分析法:状态表示&&状态计算

状态表示：
集合 所有选法/条件
属性 Max/Min/Num
状态计算：

DP优化：对代码或方程进行等价变形

背包问题

题意

有$\text{n}$个物品和一个容量为$\text{m}$的背包，物品不可分割，每个物品的价值和体积分别为$w_i$ $v_i$，求能获得的最大价值
1.01背包 每个物品最多用1次（对于某个物品，只有选与不选两种可能）
2.完全背包 每个物品有若个个
3.多重背包 第i个物品最多用$s_i$次
4.分组背包 有若干组物品，每组中最多只能选1个物品

01背包

状态表示：
集合:从前i个物品中选总体积不超过j的所有选法
属性：max
状态计算：集合划分 不含第i个物品($f_{i,j}=f_{i-1,j}$) && 含第i个物品($f_{i,j}=f_{i-1,j-v_i}+w_i$)

ans:$f_{n,m}$(从n个物品中选择总体积体积不超过m)
代码时间复杂度$O(nm)$，空间复杂度$O(nm)$

for(int i = 1 ; i <= n ; i ++)
    for(int j = 0 ; j <= m ; j ++){
        f[i][j] = f[i-1][j];
        if(j >= v[i])f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//在保证当前容量能装下该物品进行比较
    }

优化空间————滚动数组
二维->一维？
注意到求$f[i]$层的时候只用到$f[i-1]$层，而之前的层都没有用了。同时$f[i-1]$层里用到的j是小于等于当前的j的
修改一下？

    for(int i = 1 ; i <= n ; i ++)
    for(int j =  v[i]; j <= m ; j ++){
        //f[i][j] = f[i-1][j];因为删去i后变成了f[j]=f[j]，恒等式，就不必要了
        f[j] = max(f[j],f[j-v[i]]+w[i]);
    }

然而这样求，发现在同一层中由于是从小到大枚举，导致$f_{j-v_i}$在$f_j$前求，这样$f_j$用到的是$f_{i,j-v_i}$,而不是$f_{i-1,j-v_i}$
Solution:从大到小枚举
在同一层中，$f_j$比$f_{j-v_i}$先枚举，此时$f_j$用到的$f_{j-v_i}$实际是上一层的，符合我们的需求。
优化后空间复杂度为$O(n)$

完全背包

状态表示：
集合:从前i个物品中选总体积不超过j所有选法
属性：max
状态计算：
集合划分 不选($f_{i,j}=f_{i-1,j}$) 选1个，选2个……(选k个：$f_{i,j}=f_{i-1,j-k \times v_i}+k \times w_i$)
ans:$f_{n,m}$(从n个物品中选择总体积体积不超过m)
时间复杂度$O(nmk)$，空间复杂度$O(nm)$
其中时间复杂度最差$O(nm^2)$ ——TLE
优化
朴素算法转移方程：
f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-v[i] $\times$ 2]+w[i] $\times$ 2,f[i-1][j-v[i] $\times$ 3]+w[i] $\times$ 3$\ldots$)
f[i][j-w[i]] = max(f[i-1][j-v[i]],f[i-1][j-v[i] $\times$ 2]+w[i],f[i-1][j-v[i] $\times$ 3]+w[i] $\times$ 2$\ldots$)
注意到标粗的部分，之间的区别仅仅是上面比下面多了一个w[i]，也就是说，f[i][j]后面的那一堆可以通过f[i][j-v[i]]+w[i]来解决，即：
$f_{i,j} = max(f_{i-1,j},f_{i,j-v_i}+w_i)$
继续优化
滚动数组：容易发现$f_{i,j-v_i}$要在$f_{i,j}$之前算(和01背包相反)
所以直接删去i，循环的顺序（从小到大）恰好满足需求
最终时间复杂度$O(nm)$，空间复杂度$O(n)$

多重背包

状态转移方程$f_{i,j} = max(f_{i,j},f_{i-1,j-v_i \times k}+w_i \times k)$其实和完全背包一样的
多重背包问题Ⅰ数据范围那么小暴力就行了奥力给$O(n^3)$
开始优化不优化在大数据前就死了
优化0.空间的优化
把多重背包写成一维的，其实和01背包类似，j需要倒着循环（原理同01背包），只不过需要多加一层循环来决定选几个物品
优化0.完全背包的方法?
多重背包和完全背包这么像，用完全背包的优化方式优化多重背包可行吗？Too young too simple
多重背包的转移方程
f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-v[i] $\times$ 2]+w[i] $\times$ 2$\ldots$f[i-1][j-v[i] $\times$ s[i]]+w[i] $\times$ s[i])
f[i][j-v[i]] = max(f[i-1][j-v[i]],f[i-1][j-v[i] $\times$ 2]+w[i]$\ldots$f[i-1][j-v[i] $\times$ s[i]+w[i] $\times$ (s[i]-1),f[i-1][j-(s+1) $\times $ v]+w[i] $\times$ s[i])
然后发现多出来的斜体部分成功地把优化梦想打破……

完全背包在这里的区别是
设当前使用物品最多能用s次（注意这里的s与体积有关，不是限定的）
则f[i][j] = max(...f[i-1][j-v[i]×s]+w[i]×s)
而f[i][j-v[i]] = max(...f[i-1][j-v[i]×s]+w[i]×(s-1))
因为当前的j最多能用s次物品，所以j-v[i]最多能用(s-1)次，j-v[i]-(s-1)×v[i]=j-v[i]*s
所以在完全背包中后面的部分是完全一一对应的。
而多重背包，s是限制的，与体积无关，所以不能保证一一对应关系

优化1.二进制
超时的主要问题是，在把多重背包转换成01背包的时候，多了一重循环，这个循环是挨个枚举物品个数的。
二进制表示
例如，对15来说，可以将其打包成1，2，4，8来表示1-15种任意一个数
原理是$15_{(10)}=1111_{(2)}$，而$1=2^0,2=2^1,4=2^2,8=2^3$
这样一来，原本要循环15次，现在只需要循环4次就可以了
复杂一点的情况:
对200来说，我们可以打包成1，2，4，8，16，32，64，64 此时我们可以表达出0-127,然而加上128范围就到了256，超过200，此时应该加上的数是73（200-127=73)
于是原本$O(n^3)$级算法变成了$O(n^2logn)$
然后此题变成了一个纯01背包
代码实现————预处理

scanf("%d%d",&n,&m);
for(int i = 1 ; i <= n ; i ++){
    scanf("%d%d%d",&a,&b,&s);
    int k = 1;
    while(k <= s){
        v[++cnt] = a*k;
        w[cnt] = b*k;
        s -= k;
        k <<= 1;
    }
    if(s > 0){
        v[++cnt] = a*s;
        w[cnt] = b*s;
    }
}
n = cnt;

优化2.单调队列
由于太菜不会

分组背包

多了一重循环来选择物品，类似于01背包。
分组背包也是可以用滚动数组来进行空间优化。