多重背包

完全背包加上数量限制

优化1：类似二进制打包物品 转换成01背包

优化2：

$$\begin{array}{c}f[i,j]=max(f[i-1,j-v]+w,f[i-1,j-2v]+2w,...,f[i-1,j-sv]+sw)\\ f[i,j-v]=max(f[i-1,j-2v]+w,f[i-1,j-3v]+2w,...,f[i-1,j-sv]+(s-1)w,f[i-1,j-(s+1)v]+sw)\\ f[i,j-2v]=max(f[i-1,j-3v]+w,f[i-1,j-4v]+2w,...,f[i-1,j-sv]+(s-2)w，f[i-1,j-(s+1)v]+(s-1)w，f[i-1,j-(s+2)v]+sw)\end{array}$$

多重背包中求滑动窗口的最大值

完全背包中求所有前缀的最大值

滚动数组 因为用到上一层的状态且使用了滑动窗口，所以每次备份上一层的状态