以下内容是笔者根据背包九讲以及B站up主大雪菜讲解视频后总结的一些笔记，欢迎各位同道中人不吝赐教
附上链接：
CSDN博友分享(https://blog.csdn.net/yandaoqiusheng/article/details/84782655)
B站学习视频(https://www.bilibili.com/video/BV1qt411Z7nE)
1. 01背包问题（每个物品只能选或者不选）
f[i][j]表示只看前i个物品，总体积是j的情况下的最大总价值。
暴力搜索：
res=max{f[n][0\~V]} 动态规划：确定状态只有0和1，写出状态转移方程
a. 0（不选第i件物品）
f[i][j][0]=f[i-1][j]; //从i-1到i没有改变b. 1（选了第i件物品）
f[i][j][1]=f[i-1][j-Ci]+Wi; //放了i后的体积是j，i-1的体积需要减去i的体积合并状态：
f[i][j]=max(f[i-1][j],f[i-1][j-Ci]+Wi)
时间复杂度：O(NV) 空间复杂度：O(NV)
优化：第i件物品的状态只跟i-1的状态有关，即只需要用上一层数组，不需要全部数组
a. 滚动数组（新的数据覆盖旧的数组，即只保留上一层数组，所以只需要两行数组）
b. 一维数组 f[i]表示体积是i的情况下的最大总价值
原状态方程先改成：
f[j]=max(f[j],f[j-Ci]+Wi)假如枚举到：i = 3, j = 8, v[3] = 5, w[3] = 1
二维：
dp[3][8] = max(dp[2][8], dp[2][3] + w[3]) // 此时的dp[2][8]和dp[2][3]都是上一轮的状态值一维：
dp[8] = max(dp[8], dp[3] + w[3]) //我们要保证dp[8]和dp[3]都是上一轮的状态值 按照逆序的顺序，一维dp数组的更新顺序为：dp[8], dp[7], dp[6], … ,dp[3]，也就是说，在本轮更新的值，不会影响本轮中其他未更新的值！较小的index对应的状态是上一轮的状态值！
如果按照顺序进行更新，dp[3] = max(dp[3], dp[0] + w[0])，对dp[3]的状态进行了更新，那么在更新dp[8]时，用到的dp[3]就不是上一轮的状态了，不满足动态规划的要求。
tips：初始化时，如果将f都初始化为0则输出f[V],因为每一个容量都能由状态方程计算最大值，即此时f表示为<=V时的最大总价值；若只初始化f[0]为0，则其余f为INF，只有放入物品后对应的那些容量能够求取最大值，其余容量均为INF，所以此时f表示容量恰为V时的最大值，因此需要遍历所有f找最大值
2. 完全背包问题（每个物品不限数目）
二维数组：跟01背包问题类似，只不过多了选择k件，k最大为V/Ci，即：
f[i][j]=max(f[i-1][j],f[i-1][j-kCi]+kWi)一维数组：f[i]依旧表示在总体积是i的条件下的最大价值
f[j]=max(f[j],f[j-Ci]+Wi)一般方法：在01背包的基础上，再嵌套一层循环k从0~V/Ci
优化：在01背包的基础上，将体积从Ci~V循环，即按顺序的顺序，与01背包恰好相反
从01背包我们知道，按顺序更新f时，f[j-Ci]在本轮已经更新过，也就是说f[j-Ci]是i时刻的状态而不是i-1时刻的状态，即此时第i件物品已经放入，且可能已放入多件
3. 多重背包问题（每件物品最多放置s件）
暴力解法：在01背包的基础上，加一层循环，件数从0~s循环
f[j]=max(f[j],f[j-Ci]+wi,f[j-2\*ci]+2\*ci,...f[j-s\*ci]+s\*wi)优化：将多重背包问题转化成01背包问题，将s件拆出来放进可选物品，每个物品只能选或者不选，怎么拆？
a. 二进制优化（对于任意一个数s，s以内的所有数都能用几个数的和表示，最少需要几个数）
每个数可选可不选，n个数可以表示2^n个数，2^n>=s，所以n=floor(logs/log2)，但是当s不是整数幂的时候会多出来一部分，对于最后一个数，用s-1-2-4…一直到负数停止。
例如：0~7可以用1、2、4表示；0~10在0~7的基础上扩展了3，所以可以用1、2、4、3表示，或者用s-1-2-4=3得到
此题就转化成物品个数被拆成n*log(s)个的01背包问题;
b. 单调队列优化（第二层循环将体积j归类，按j%Ci分类，对于f[j-k*Ci]只能从与Ci取相同余数的那一类状态转化来）
f[j]=max(f[j-Ci]+Wi,f[j-2\*Ci]+2\*wi,...f[j-k\*Ci]+k\*wi)转化成单调队列（k个数的滑动窗口）里面找最大值
f[j+Ci]=max(f[j]+wi,f[j-Ci]+Wi,...)4. 混合背包问题（物品分三类，一次，无限次和有限次）
将多重背包问题拆分转化成01背包问题，问题就转化成01背包和完全背包问题，根据物品属于哪一类，将容量从小到大或者从大到小枚举
5. 二维费用的背包问题（在01背包基础上每个物品属性扩展了重量）
增加一维表示重量 f[i][j]表示在体积为i重量为j的情况下的最大总价值,
因为是01背包问题，多一层循环，从大到小枚举体积和重量
f[i][j]=max(f[i][j],f[i-a][j-b]+c)6. 分组背包问题（N组物品，每组物品只能选一种物品）
本质还是01背包问题，每一组只能选或者不选，如果选的话，一组就退化成某一个物品,针对选择哪一个物品再增加一层循环
f[j]=max(f[j],f[j-c[0]]+w[0],f[j-c[1]]+w[1],...f[j-c[s-1]]+w[s-1])体积依旧从大到小循环
多重背包实际上是分组背包的一种特殊情况，每一组选择k个，实际就是将这k个打包成一个物品
7. 背包问题求方案数（01背包基础上最优解的方案数）
增加一个数组g[i]表示体积恰好为i时的方案数，此时f在初始化时只能把f[0]初始化为0，其余初始化为-INF；
f[j]=max(f[j],f[j-ci]+wi)
g[j]=f[j]==(f[j-ci]+wi)?g[j]+g[j-ci]:(f[j]\>(f[j-ci]+wi)?g[j]:g[j-ci])然后遍历所有f找最大值，将最大值对应的g累加起来
8. 背包问题求具体方案（在7的基础上输出所有可行方案中字典序最小的）
根据7求出的最优解反推第i个物品有没有选
f[i][j]表示只看前i个物品，总体积是j的情况下的最大总价值
f[i][j]=max(f[i-1][j],f[i-1][j-ci]+wi)最优解一定为f[n][m]
因而从后往前枚举物品，根据判断f[n][m]和f[n-1][m]以及f[n-1][m-c]+w中哪个数相等，从而判断n有没有选，如果两者相等，则表示i选或不选都可
优化：题目要求输出字典序最小的解，假设存在一个包含第1个物品的最优解，为了确保字典序最小那么我们必然要选第一个。那么问题就转化成从2～N这些物品中找到最优解。之前的f(i,j)记录的都是前ii个物品总容量为jj的最优解，那么我们现在将f(i,j)定义为从第i个元素到最后一个元素总容量为j的最优解。接下来考虑状态转移：
f(i,j)=max(f(i+1,j),f(i+1,j−v[i])+w[i])两种情况，第一种是不选第i个物品，那么最优解等同于从第i+1个物品到最后一个元素总容量为j的最优解；第二种是选了第i个物品，那么最优解等于当前物品的价值w[i]加上从第i+1个物品到最后一个元素总容量为j−v[i]的最优解。
9. 有依赖的背包问题（类似于课程表，有前序物品要选的01背包问题）
背包问题和树形结构结合 依旧使用二维数组f[i][j] 从根节点从上往下递归
每个节点计算对应子节点下面不同体积下的最大价值，从其中选价值最大的那一组，从而转化成分组背包问题
