//笔者水平有限，望海涵
复习视频课 背包九讲 + 闫式dp法前15分钟复习dp做题思路
1----01背包问题
f[i][j]状态表示:只用前i个物品，在总体积为j(0~v)的背包中最大价值，属性就是最大价值
状态计算:
1.不选第i个物品f[i][j]=f[i-1][j]
2.选第i个物品f[i][j]=f[i-1][j-v[i]]
f[i][j]=max{1,2};
初始化:f[0][0]=0，体积为0，最大价值就是0
优化成一维f[j]
枚举j时从大到小枚举
当j>=v[i] f[j]=max(f[j],f[j-v[i]]+w[i]);
小注解:
记f[k]或f[n][k]为1~j中的最大价值,k为此时的体积容量了，m为最大容量
那么除f[0]或者f[0][0]=0,其余f全赋值为负无穷，则f[n][k]得到的是在前n个物品中在1~j体积 中恰好得到最大价值时体积为k，而全初始化为0，f[n][k~m]都指向体积1~j得到的最大价值
因此:
1.除f[0]外f[1~m]或者f[0][1~m]全部赋值为负无穷,因为选前0个物品,只有体积为0恰好达到最大价值为0，其余的都是-INF.
如果我们要得到答案需要遍历1~j找到最大的那个价值
2.如果全部赋值为0，则直接输出f[k~m]或者f[n][m];
原因在于容量k为最优价值，m-k就是多出来没有选物品放置的,，m要达到最大，选择的物品应当和容量为k的一模一样，必须要从f[m-k]走,所以通过f[m-k]+f[k]与f[0]+f[k]可以区分出来
01背包题目
01背包题解
----------
2----完全背包问题
f[i][j]状态表示:只用前i个物品，在总体积为j(0~v)的背包中最大价值，属性就是最大价值
状态计算:
1.不选第i个物品f[i][j]=f[i-1][j]
2.选第i个物品f[i][j]=max(f[i-1][j-v]+w,f[i-1][j-2*v]+2 * w…,f[i-1][j-k * v]+k * w)
f[i][j]=max{1,2};
初始化:f[0][0]=0，体积为0，最大价值就是0
优化：
因为每个物品可以选无限次，因此，我们不得不用三重循环
但是通过推导:
f[i][j]=max(f[i-1][j-v]+w,f[i-1][j-2*v]+2 * w…,f[i-1][j-k * v]+k * w)
f[i][j-v]=max(f[i-1][j-2 * v]+w,f[i-1][j-3 * v]+2 * w…,f[i-1][j-k * v]+(k-1)* w)
转化为二维
f[i][j]=max(f[i-1][j],f[i][j-v]+w);
然后优化成一维，类似于01背包
f[j]=max(f[j],f[j-v[i]]+w[i]);
小注解:
由于一维优化f[i][j]=max(f[i-1][j],f[i][j-v]+w),max中都是同一层的，所以j-v[i]应该先算出来，则j应该从小到大
完全背包题目
完全背包题解
----------
3----多重背包问题
多重背包Ⅰ中:
f[j]状态表示:总体积为j的情况下,最大价值
状态计算:
f[j]=max(f[j],f[j-kv[i]+kw[i]);(k=0~s[i])
小注解:
暴力写法类似于完全背包的暴力写法二维数组，三重循环，
优化一维写法就是类似于01背包优化但是要加一层循环枚举个数k
多重背包Ⅰ背包题目
多重背包Ⅰ题解
多重背包Ⅱ中:
状态计算:
f[j]=max(f[j],f[j-v[i]+w[i]);
小注解:
由于物品N最多为1000，数量为2000，容量最多为2000，因此不能用三重循环，使用
二进制优化成n(log以2为底s向上取整)的复杂度，然后直接当成01背包问题处理
疑问:为什么不能当完全背包处理?
f[i , j ] = max( f[i-1,j] ,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-v] ,f[i-1,j-2v]+w, .....f[i-1,j-Sv]+(S-1)w,f[i-1,j-(S+1)v]+Sw )
多出来的一项是由于容量j-v若大于等于sv，则会装满，而上面的式子由于个数限制装不了
疑问:二进制优化即用二进制一定能够表达出我们想要的这种物品的个数吗?
比如说表达0~7，我们可以用1，2，4三个数表示出来因为7的二进制各位为111，三个二进制位
我们用1，10，100，这三个数自由组合就能表达0(一个都不选)~111范围内的所有数
所以每一个物品假如有s个，s=200,可以分成2^0,2^1…,2^6,1到2^6累加为127，表示出0~127，
剩下的直接用200-前面二进制累加，剩下的73分为一组，则可以表示完0~200的范围任意数
疑问:分完组如何计算?
把每个物品按照二进制分好组后，看成有n*(log以2为底s向上取整)个物品，都只能选一次，当作01背包处理即可
多重背包Ⅱ背包问题
多重背包Ⅱ题解
----------
多重背包Ⅲ中:
f[i][j]状态表示:选前i个物品,总体积为j的情况下的最大价值
优化为一维
f[j]状态表示:总体积为j的情况下,最大价值
状态计算:
f[i][j]=max(f[i-1][j],f[i-1][j-kv[i]+kw[i]);(k=0~s[i])
小注解:
在多重背包Ⅰ中有如下思路:
暴力写法类似于完全背包的暴力写法二维数组，三重循环，
优化一维写法就是类似于01背包优化但是要加一层循环枚举个数k
但是在多重背包Ⅲ中N最大范围在10000,s[i]和v最大在20000，三重循环必定超时
因此，我们可以用单调栈来优化
假设总体积为m
1遍历n个物品,当遍历到第i个物品，我们需要把0~m所有最大价值更新一下
2因为0~m对v[i]取余，我们可以把0~m容量从[0,v[i])分成v[i]这么多组，每一组最大价值需要更新可以得到
f(i,r)=f(i−1,r)
f(i,r+v)=max(f(i−1,r+v),f(i−1,r)+w)
f(i,r+2v)=max(f(i−1,r+2v),f(i−1,r+v)+w,f(i−1,r)+2w)
···
f(i,r+(s−1)v)=max(f(i−1,r+(s−1)v),⋯,f(i−1,r)+(s−1)w)
f(i,r+sv)=max(f(i−1,r+sv),f(i−1,r+(s−1)v)+w,⋯,f(i−1,r)+sw)
···
f(i,j−2v)=max(f(i−1,j−2v),f(i−1,j−3v)+w,⋯,f(i−1,j−(s+2)v)+sw)
f(i,j−v)=max(f(i−1,j−v),f(i−1,j−2v)+w,⋯,f(i−1,j−(s+1)v)+sw)
f(i,j)=max(f(i−1,j),f(i−1,j−v)+w,⋯,f(i−1,j−sv)+sw)
因为每一个体积都只从当前组的其他状态转移过来，同时受物品个数s影响
因此用单调栈来维护一个大小为s[i]的滑动窗口,并不断更新在选前i个物品体积为0~m的最大价值
多重背包Ⅲ背包题目
多重背包Ⅲ题解
参考的题解Ⅰ
参考的题解Ⅱ
4----混合背包问题
f[i][j]状态表示:选前i个物品容量为j时候,可以得到的最大价值
状态计算:分情况而定看是完全背包还是01或者多重背包问题
完全背包:当j>=v[i]时,f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);当j<v[i],f[i][j]=f[i-1][j];
多重背包:1.二进制优化转化为01背包
01背包:s=1 f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
小注解:
当我们选择第i个物品时，我们不需要去考虑前i-1个物品类型是完全背包类型还是01，多重背包，只考虑
第i个物品是什么类型，而01背包我们可以把它s设置为1和多重背包一块处理了
混合背包问题
混合背包题解
5----二维费用的背包问题
二维费用意思是限制最大价值条件有两个，容量和重量
f[j][k]状态表示:在选第i个物品,在背包体积为j，能承受的最大重量k的情况下能得到的最大价值
状态计算:
f[j][k]=max(f[j][k],f[j-v[i]][k-m[i]]+w[i]);
小注解:
类似于01背包，加了个限制条件，按照朴素版01背包我们可以写成三维数组形式，但是01背包问题是可以优化成一维的，那就对应的可以把二位费用的背包问题优化为二维的
01背包状态方程:
f[i][j]=max(f[i-1][j],f[i-1][j-v]+w);
优化:f[j]=max(f[j],f[j-v]+w);
01背包加个限制条件:
f[i][j][k]=max(f[i-1][j][k],f[i-1][j-v[i]][k-m[i]]+w[i])
优化:f[j][k]=max(f[j][k],f[j-v[i]][k-m[i]]+w[i]);
二维费用的背包题目
二维费用的背包题解
6----分组背包问题
f[i][j]状态表示:只选前i组中的一个物品，在背包最大容量为j的情况下得到最大价值
状态计算:
假设每一组有s个物品,用每一组的物品更新i层各个容量j得到的最大价值
f[i][j]=max(f[i-1][j],f[i-1][j-v[0]]+w[0],f[i-1][j-v[1]]+w[1]…,f[i-1][j-v[s]]+w[s])
小注解:
先遍历n个组,每个组设有s个物品,再遍历容量j,在这第i层每个容量j再遍历每个物品找到使目前遍历到的容量j的能够取到最大价值的物品或者是不选该组的物品
为什么可以用01背包优化?
只用到了第i列与i-1列。
每一组内s个物品
分组背包题目
分组背包题解
参考题解
7----背包问题求方案数
f[i][j]状态表示:在选前i个物品，体积为j的情况下，恰好能够取到的最大价值
状态计算:
f[i][j]=max(f[i-1][j],f[i-1][j-v]+w);
一维优化
f[j]=max(f[j],f[j-v]+w);
小注解:
1当f[i][j]/f[j]表示在选第i个物品,体积为j,恰好得到该体积的最大价值
g[i][j]的状态表示:在选取前i个物品,恰好体积为j时取到的最大价值的方案数
可以从三个方向转移过来
1.当f[i][j]=f[i-1][j],且f[i-1][j]==f[i-1][j-v]+w,则g[i][j]=g[i-1][j]+g[i-1][j-v]
2.当f[i][j]=f[i-1][j],且f[i-1][j]!=f[i-1][j-v]+w,则g[i][j]=g[i-1][j]
3.当f[i][j]=f[i-1][j-v]+w,且f[i-1][j]!=f[i-1][j-v]+w,则g[i][j]=g[i-1][j-v]
初始化:g[0][0]=1,f[0][1~m]=-INF
输出:在f[n][0~m]中找到最大价值，在遍历一次f[n][0~m],与最大价值相同的f[n][j]对应的g[n][j]加上
2当f[i][j]/f[j]表示在选第i个物品,得到体积<=j的最大价值
g[i][j]的状态表示:在选取前i个物品,体积<=j时取到的最大价值的方案数
状态计算和上面一样
初始化:f全为0,g[0][0~m]=1;
输出结果就是g[n][m]
为什么g[n][m]是结果?
假如体积为k，得到最大价值f[n][k],因为是恰好体积为k得到的最大价值
我们加个偏移量x,令x+k=m,f[n][m],由于最开始是从f[0][x],转移过来的，因此g[n][k]的值一定包含在g[n][m]中，因为他们可以被类似的状态转移过去
如果有多个f[n][k],即都是最大价值一样，且恰好能得到体积是k,那这几个g[n][k都会被包含在f[n][m]中
背包问题求方案数题目
背包问题求方案数题解
8----背包问题求具体方案
f[i(n~1)][j]状态表示:从后i个物品选,当体积为j时取得的最大价值
状态计算:
f[n][m]=f[n-1][m],说明没有取第n-1个物品
f[n][m]=f[n-1][m-v[n]]+w[n],说明取了第n个物品
小注解:
找出字典序小的那一组选法,我们可以逆向枚举物品n~1,从而在判断是否选了该物品时，可以从1~n判断,因为正向枚举物品，我们只有从f[n][m]得到最大价值，而只有从n~i来逆向枚举物品是否选择
如果找到一个i,j>=v[i]&&f[i][j]=f[i+1][j-v[i]]+w[i],需要输出i的值，并且时j减去v[i]
背包问题求具体方案题目
背包问题求具体方案题解
9----有依赖的背包问题
f[u][j]状态表示:以u为根节点的子树，选上u的且体积不超过j所有选法的最大价值
状态计算:
初始化时令j>=v[u]的f值:f[u][j]= w[u]
f[u][j] = max(f[u][j], f[u][j - k] + f[son][k])
小注解:
三维方程如下:
f[u][i][j]=max(f[u][i][j],f[u][i-1][j-k]+f[x][x_son][k])
(x是u的子节点，x_son是u这个节点的子节点总个数)
最终只会用到当前节点x的上一层状态f[u][i-1][j-k]，和子节点f[x][x_son][k]的最终状态
因为f数组后二维就是分组背包问题，因为每个分配体积k只能用一次可以通过01背包化为一维，就是得逆序枚举体积j
优化为二维
f[u][j] = max(f[u][j], f[u][j - k] + f[son][k])
这里是分组背包的步骤，每个子节点是一个物品组，每个子节点的不同体积代表组内的物品，所以这里在枚举如果选择son这个物品组中的第k个物品，最大价值是多少。
思路:
以u为树根的所有子节点个数看作分组背包的组数处理，然后枚举体积j，并枚举当前子树的物品组k,k(当j为v[u]~m,k为[0,j-v[u]],当j为0~m-v[u]，k=[0,j],实际都是k=[0,m-v[u])，f[son][k]就相当于w[son,k],
只看后面两个[i][j]代表的是在前i个组中选，总体积不超过j的所有集合，属性max,就相当于分 组背包问题
