题目：有$n$个物品，背包体积为$m$，$v[i]$代表第$i$个物品体积，$w[i]$代表第$i$个物品的价值
注意这里只写出状态定义和状态转移公式，有些判断就没写了
注意dp数组元素的生成顺序，要先生成小问题再生成大问题，这就决定了循环顺序，特殊的像区间DP的外层循环就必须是长度len
对于滚动数组优化，如果用到了$i-1$层的更小状态，那么就必须倒序循环枚举状态；如果只用到了$i$层的更小状态，那么就只能顺序循环枚举状态
所有背包问题都是①先循环物品，②再循环体积（多一个其它条件就多一维，多循环一层）③再枚举决策（可能无需循环）
背包枚举的都是$dp$数组的状态空间，搞清定义
01背包
题目：每个物品只有选与不选
$f(i,j)$表示前$i$个物品装进体积为$j$的背包的最大价值
最后一个不同点：第$i$个物品选还是不选
注意，左边都是$i-1$子问题，想清楚式子的含义！
空间优化（滚动数组）：$f(j)=max(f(j),f(j-v[i])+w[i])$，由于用到上层dp值（在滚动数组中即为编号较小的未更新元素），所以$j$必须倒序循环枚举
完全背包
题目：每件物品可以选无限次
$f(i,j)$表示前$i$个物品装进体积为$j$的背包的最大价值
最后一个不同点：第$i$个物品不选，第$i$个物品选1个，第$i$个物品选2个，…..
$f(i,j)=\max\{f(i-1,j),f(i-1,j-v[i])+w[i],f(i-1,j-2v[i])+2w[i]+\cdots\}$
等价变形：$f(i,j-v[i])=\max\{f(i-1,j-v[i]),f(i-1,j-2v[i])+w[i],f(i-1,j-3v[i])+2w[i]+\cdots\}$
回代原式（时间优化）：
注意：这里就背包体积$j$只能从小到大循环了，因为用到了当层$i$下、$j$更小的子问题解，而以前用到的都是$i-1$层的子问题解
空间优化（滚动数组）：$f(j)=max(f(j),f(j-v[i])+w[i])$，用到了本层编号较小的dp值，所以$j$必须正序循环枚举
多重背包
题目：每个物品最多有$s[i]$件
$f(i,j)$表示前$i$个物品装进体积为$j$的背包的最大价值
最后一个不同点：第$i$个物品不选，第$i$个物品选1个，第$i$个物品选2个，…..，第$i$个物品选$s[i]$个
$f(i,j)=\max\{f(i-1,j),f(i-1,j-v[i])+w[i],f(i-1,j-2v[i])+2w[i]+\cdots+f(i-1,j-s[i]×v[i])+s[i]×w[i]\}$
由于每个物品的选择上限不同，所以不能等价变形，需要多写一层循环遍历第$i$个物品可能的选择个数$0$到$s[i]$来求，也就是多了个决策循环；（但转化为01背包就可以不循环决策了，见下面优化方法）
时间优化：可以将同一个物品的$s[i]$份拆开变成$s[i]$个1个物品，这就转化为01背包问题了。但直接拆复杂度是不变的，可以通过二进制的方法来拆，将$s$个物品打包成$\log s$个物品组，用它们可以凑出$0$到$s$的任意一个数，减少01背包子问题数量，这样时间复杂度由$O(nsv)$优化到$O(n\log s v)$。举个例子，我们原来想要用01背包表示“第$i$个物品最多可选7个”，就需要用$[1,1,1,1,1,1,1,1]$来表示，然后用01背包dp来解；而现在我们知道7的二进制编码为$0111$，那么第$i$个数就只需要$[4,2,1]$来表示，那么我们dp的时候会自动组合这三个堆，比如算得$dp(i,j)$下$i$选3个是最优解，那么dp实际上就是选择了$2$和$1$，没选$4$。这里的核心就在于：二进制的组合可以以较低的位数表达（编码）任意一位十进制
混合背包
题目：有三类物品，第一类：只能用1次（01背包）；第二类：可以用无限次（完全背包）；第三类：物品最多只能用$s[i]$次（多重背包）
只需要判断当前物品是什么类，然后转移的时候按照对应类的物品去转移即可
可以将多重背包转化为01背包，那就只需要判断两种情况了（01、完全）
二维费用背包
题目：除了体积限制以外还有其它限制，背包重量不能超过$M$，每个物品的重量为$m[i]$（基于01背包）
$f(i,j,k)$：第$i$个物品装进体积是$j$，重量是$k$的背包的最大价值
$f(i,j,k)=\max \{f(i-1,j,k),f(i-1,j-v[i],k-m[i])+w[i]\}$
需要进行三重循环：前$i$个物品、背包最大体积$j$、背包最大重量$k$
空间优化（滚动数组）：$f(j,k)=\max\{f(j-v[i],k-m[i]),f(j,k)\}$，用到上一层$i$，需要从大到小枚举体积和重量
二维背包也可以基于完全背包等，基本都是一样改，多一个条件，状态方程就多一维，就多一层枚举循环
ATT：我们枚举的是状态空间，多的一层枚举循环是背包重量不同造成状态维度多了一维，也就是说子问题更多了
分组背包
题目：物品分为$N$组，同一组内物品只能选一件
先遍历组，再遍历决策，求最值
$f(i,j)$：从前$i$组物品里选，且体积不超过$j$的背包最大价值
$v[i][k]$即为第$i$组第$k$个物品，要先构造好；第$i$组一共用$s$个物品
$f(i,j)=\max\{f(i-1,j),f(i-1,j-v[i][0])+w[i][0],f(i-1,j-v[i][1])+w[i][1],\cdots,f(i-1,j-v[i][s])+w[i][s]\}$
需要进行三次循环：遍历组$i$，背包体积$j$，遍历组内物品编号$k$
很像多重背包问题，公式也像，其实多重背包问题就是分组背包问题的一种特殊情况，但分组背包无法进行优化
背包问题求方案数
题目：一般背包问题是求最大最小价值，这里还需要求最优价值下的方案数
在01背包的基础上，①需要新开一个数组，两个dp同时进行（最优解dp、方案数dp）且需要利用最优解的dp状态去推方案数dp状态②决策的时候需要判断选$i$和不选$i$两种选择的总价值的大小关系，如果选$i$与不选$i$的价值一样大则最大价值的方案数多了$g(i-1,j−v[i])+g(i-1,j)$种；若不选第$i$个物品更大，则多了$g(i-1,j)$种；若选第$i$个物品更大，则多了$g(i-1,j−v[i])$种③方案数dp的状态方程如何理解？因为$g(i,j)$是$i$个物品在背包体积$j$下的最佳方案数，可由②中所述的三种选法组成，这里对$g$的集合划分、最后一个不同点 是不同的！
$f(i,j)$：前$i$个物品，背包体积是$j$的情况下的背包最大价值（以前是体积最多是$j$的背包方案数，这样的话可能体积用不完，但是也能转移）
$g(i,j)$：前$i$个物品，背包体积是$j$的情况下的背包方案数（注意转移条件，最后一个子问题划分为三类）
初始化的时候，$g(i,0)=1$，$f(i,j)=0$，最后的最优解的方案数就是$g(i,j)$
同样可以用滚动数组优化，这样最后也就省去了同$i$相加的步骤，只需要两个数组$f(i)$和$g(i)$
注意：这个问题也可以换成完全背包，分组背包，但是思想是一样的：利用最优解的dp状态去推方案数的dp状态，根据最优解方程，方案数状态方程只能选择最优解对应的方案数来进行状态转移，如果相等则加和再转移
背包问题求具体方案
题目：一般背包问题是求最大最小价值，这里还需要求最优价值下字典序最小的方案（字典序这里指所选物品的编号所构成的序列）
要求字典序最小的方案，那首先就得先求出所有方案，我们需要记录所有的状态，就不能压缩为一维了
我们需要反推方案，即在我们知道$f(i,j)$是前$i$个物品装进容量为$j$的包的最优解的情况下，想知道第$i$个物品有没有选，我们可以通过看 $f(i,j)$是从哪个状态转移过来的来判断：① $f(i,j)=f(i-1,j)$，代表不选第$i$个物品，从$f(i-1,j)$状态转移过来；②$f(i,j)=f(i-1,j-v[i])+w[i]$，代表选第$i$个物品，从$f(i-1,j-v[i])$状态转移过来；③如果$f(i-1,j)=f(i-1,j-v[i])+w[i]$，代表第$i$个物品选不选都可以。
但是这种思路存在问题，就是本题要求编号字典序序列最小的一种方案，所以我们选的数应该越靠前越好，而这样的话我们无法实现这个需求。
所以这里我们重新定义状态：
定义$f(i,j)$：第$i$个元素以后的物品，背包总容量为$j$的最大价值（最优解），那么这里最后一个区别依然是选不选第$i$个物品，属性依然为$\max$
这样我们就做到了能早选就早选，这样的话$f(1,M)$就是字典序最小的最大价值。
于是，对于$f(i,j)$，
①$f(i,j)=f(i+1,j)$，不选第$i$个物品才能达到最优解
②$f(i,j)=f(i+1,j-v[i])$，选取第$i$个物品可以达到最优解
③$f(i,j)=f(i+1,j)=f(i+1,j-v[i])$，可选可不选，我们必选
这样我们通过遍历$i$，并且维持一个背包剩余体积$vol$，通过上述的顺着递推的方法进行判断即可求得最优解一路的方案。
举例子，如果判断②选取第$i$个物品是最优解，那么我们记录$i$，并且体积变为$vol-v[i]$，下一步转移到状态去$f(i+1,vol-v[i])$去，直到背包体积装不下剩下元素或遍历完
核心：通过看 $f(i,j)$是从哪个状态转移过来的来判断第$i$个物品选没有，然后沿着状态推就可以得到每个物品选没有（小的最优解是由大的最优解组成的）
