背包模型
【采药】
01背包
体积：时间
价值：草药价值
【装箱问题】
01背包
体积：体积
价值：体积
比较特殊，需要求剩余的最小体积，等价与求我使用所有体积，能达到的最大价值，刚好这个体积就是价值
【宠物小精灵之收服】
二维费用背包
体积：球数量
重量：体力
价值：怪物个数
最后暴力遍历一下使用所有精灵球，得到的最大收服数量，并且剩余体力最多
这里有一点：我们在打斗的过程中，体力值不能为0，所以假设我们要击败30的体力
我们就会将这个状态更新在体力为31的状态，并且一定在31这个状态里面
所以最后遍历一遍找到即可
怎么理解这个“一定”？
解释：因为30这个状态被更新的时候，当体力值上限大于30的时候，题目有解，故一定会更新在31状态里面，当体力值上限小于等于30，则无解，则不会更新，最后找解也不会找到30这个状态
【数字组合】
01背包
f[i]表示组成i这个数字的方案数，故可以使用类似01背包问题的方式来写两重循环，第二层倒着遍历
【买书】
完全背包
f[i]表示花费n元（全部花完）的所有方案数这里需要初始化f[0] = 0
第一维枚举四本书
第二维完全背包即可（值域有上限）
拓展：
如果题面要求花费n元的所有方案数（不要求全部花完），严格怎么计算？
思路历程：首先想到的是容斥，状态表示不变，但是在完全背包的时候考虑累加而不是取max，不可行，因为会有重复的方案。
最后发现，在状态表示不变的情况下，累加最后的f[1~n]即可
【货币系统1】
完全背包
f[i]表示组成面值m的方案数（一定要达到m）这里需要初始化f[0] = 0
第一维枚举所有货币
第二位完全背包即可（值域有上限）
【货币系统2】
完全背包+排序+贪心+剪枝
首先使用最小的货币单位来完全背包值域，如果这个过程中出现了等额于其他货币的金额，则这个大金额失效，可以去掉。重复这个过程，累计失效的个数，最后用n减去并输出即可
版本1暴力，版本2二进制优化，版本3单调队列优化，以下给出具体思路和证明
第一位枚举物品数量
然后我们得到该物品的体积v、价值w、数量s
我们将
f数组拆开,得到下面：
2
3
4
5
6
dp[0], dp[v], dp[2*v], dp[3*v], ... , dp[k*v]
dp[1], dp[v+1], dp[2*v+1], dp[3*v+1], ... , dp[k*v+1]
dp[2], dp[v+2], dp[2*v+2], dp[3*v+2], ... , dp[k*v+2]
...
dp[j], dp[v+j], dp[2*v+j], dp[3*v+j], ... , dp[k*v+j]我们容易知道，只有每一行中的数会相互影响，所以我们单独拿一行出来讨论
2
3
4
5
dp[j] = dp[j]
dp[j+v] = max(dp[j] + w, dp[j+v])
dp[j+2v] = max(dp[j] + 2w, dp[j+v] + w, dp[j+2v])
dp[j+3v] = max(dp[j] + 3w, dp[j+v] + 2w, dp[j+2v] + w, dp[j+3v])然后发现没有办法两项合并，所以将数据进行一些转化
2
3
4
dp[j+v] = max(dp[j], dp[j+v] - w) + w
dp[j+2v] = max(dp[j], dp[j+v] - w, dp[j+2v] - 2w) + 2w
dp[j+3v] = max(dp[j], dp[j+v] - w, dp[j+2v] - 2w, dp[j+3v] - 3w) + 3w可以发现，虽然dp原数组不是对其的，但是减去一个偏移量就对其了
每个数的偏移量可以通过下标算出来
我们思考维护一个单调队列（下降序列），有效项数不能超过
s(当前物品的数量)同时我们只是需要前s项的最大值（已经减去偏移量）来更新自己
所以我们单调队列中存储的是具体的背包体积k
当队尾的
q[tt换算成减去偏移量后小于当前枚举到的体积k对应的f值减去偏移量时我们就弹出队尾，知道大于或者队列为空为止
当队列为空，表示不需要前面的值来更新自己，自己本来就比他们大
当队列不为空，取队头，来更新
f[k]。由于如果一直直接在
f数组上更新的话，可能导致最后的结果是由于两次方当前物品得来举例证明：
2
f[k] = max(f[k], g[q[hh]] + (k-q[hh])/v*w);我觉得该题难点在于需要理解为什么单调队列中要存放体积，为什么用体积搞一搞就能保证“有序”，以及怎么通过体积得到偏移量。
这里简略解释一下（弱弱）
尽管单调队列里面存放的是体积（v），但是其实是按照
v的“性质”排序，这个性质就是f[v]-偏移量，就能找到前面有效短里面的max，也就是上面的代码段三种的哪个图，然后对应下面的状态转移，加上代码段三种每一句的后缀（ + ｘ＊ｗ）来转移
解释：
当单调队列种有元素时，队头就是max（已带偏移量），
g[q[hh]]：花q[hh]体积得到的最大价值
(k-q[hh])/v*w：两个状态之前相隔的v的组数，乘以w为什么这两个能更新
f[k]:因为单调队列中的体积是按照他们的性质排序的，我们使用他的队头，使用为他队头对应的哪个状态最大，所以我们使用这个“数字”，我们回到代码块三，假设我们现在在讨论最后一行，我们的队头中是里面的某一个状态，容易看出来，里面所有状态，最后都要加上括号外面的偏移量，所以这里我们只需要找到里面最大的即可，其他的就不用管了。
下面证明一下为什么最后只使用了最大的哪个数据对应的体积，而没有使用括号后面的偏移量：
证明:
我们将代码块三中最后一行取到这里来
假设我们选择的是第二项
dp[j+v] - w,这一项现在在单调队列队头，根据我们的状态转移方程f[k] = max(f[k], g[q[hh]] + (k-q[hh])/v*w);我们发现
dp[j+v] - w + 3w = dp[j+v] + 2w,使用我们的方法：
结果惊人的相似，下面给出一个解释这个问题的思路：
我们成功选到了队头之后，能保证他是那一组里面的max，所以这个数一定会用，于是我们换一个思路，既然这个数一定会被用到，那么表示一定是从这个数转移过来的，那么当前体积和这个体积的差就全部都是当前物品凑起来的，就能够得到个数，进而得到价值，来更新数组即可。
【庆功会】
多重背包
二进制拆包或者单调队列优化都可
【混合背包问题】
混合背包，三混
解法一：多重背包二进制拆包，于01一起做01，完全背包单独完全
解法二：因为值域上限不大，所有进一步将完全背包也转换为多重背包，最后全变为01背包
二维费用的背包
板子题，三重循环遍历，也可以倒着来滚动数组
【潜水员】
二维费用的背包
f[i][j]：使用i氧气，j氮气，的最小重量唯一不同的是这个题是取min的过程，所以需要初始化f数组为0x3f
并且在二维背包的时候for里面不能和普通的一样（>=V[i]），而是必须到达0
因为可以出现”气体不一定全给的情况“
简而言之，就是当前有一个O1 N2 W3的罐子，也可以给
f[1][1]更新那么for里面没有限制的话，在下面是不是需要特判呢，下面给出一种解法：
2
3
4
5
6
7
8
9
{
int a, b, c; scanf("%d%d%d", &a, &b, &c);//氧 氮 重量
for(int j = w_o; j >= 0; j --)
for(int z = w_n; z >= 0; z --)
{
f[j][z] = min(f[j][z], f[max(0, j - a)][max(0, z - b)] + c);
}
}和0取max即可，这里所有本来是负数的情况表示有气体没有完全使用的情况，也就是说当前气体就以及溢出了，所以只需要当前这一个罐子，可以从0转移过来，至于可能出现一边小于0一边大于0的情况，这里不会冲突，为什么？因为当我们使用一边小于0一边大于0的情况来更新别人的时候，一边小于0一边大于0的情况在前面一定被处理过，它的f值一定不是0，所以没有问题，这里可以和普通问题一样思考即可，dp具有严格的思维性！
【机器分配】
分组背包
理解为每一个公司可以使用一个电脑，使用两个电脑……，
三重循环遍历即可。
题目需要找到一条合法路径，下面给出一种方法：
我们从倒着遍历，首先找到前面在更新n这个点的时候是从哪个状态转移过来的，如果满足下列情况，就说明满足情况，这时候要即使收敛电脑个数，继续下一次寻找。所以倒着找的意义就体现在这里。
2
3
4
5
6
7
8
9
for(int j = 1; j <= m; j ++){
if(f[i][m] == f[i-1][m-j] + q[i][j]) { <-----
way[i] = j;
m -= j;
break;
}
}
}能不能保证倒着找一定有一组解，会不会出现找到一半没有解的情况？
当然不会，假设我们找到了当前点的上一个转移点，则上一个转移点一定是再再前面的某个点更新过来，则依此思路能找到最前面的情况，也就是
f[0][0]。
【开心的金明】
01背包
体积：价格
价值：价格*重要程度
水！
【有依赖的背包问题】
树形dp+分组背包
建树、设计状态表示和状态转移
为了尽量避开容斥的环节，可以使用以下状态表示
f[u][j]：以u为根节点使用j体积并且一定使用了u点的max这样能保证不用判断子树的容斥
- 从根节点开始递归，在回溯的时候做其余操作
- 任取每一个结点，我们想要更新这个结点，就需要从子树出发
- 以每个字数的体积状态来划分，等价于选每个子树中的一种体积（一种状态）
- 至此转化为树上的分组背包问题
- 为什么要用子树的体积来划分？
- 否则则只能使用子树的转移情况来划分，也许是子树对子子树的利用，逐渐退化为爆搜
- 体积上限较小，统称为值域较小，是可以作为分组背包来枚举的
- 在用子树更新完当前根节点之后，需要将自己加入当前状态中，这里是一定要加入，故倒叙遍历一遍，强行加入
- 考虑到一定要加入，所以所有体积小于当前物品体积的状态置为0即可
【背包问题求方案数】
关于方案数的问题，一般做法为再定义一个数组
g,g中下标和f中下标严格对应，再去设计状态表示和转移方程定义
f[i]：使用了体积为i的背包能装下的最大的价值定义
g[i]：使用了体积为i并完全使用完的最大方案数于是在01背包转移的时候我们有以下转移代码
2
3
4
5
6
7
8
9
10
11
12
for(int i = 1; i <= n; i ++){//物品
int v, w; cin >> v >> w;
for(int j = m; j >= v; j --){//01背包
int maxv = max(f[j], f[j - v] + w);//先得到最大值，方便下面判断
int cnt = 0;
if(maxv == f[j]) cnt += g[j]; //不使用当前物品是max，则加上方案数
if(maxv == f[j-v]+w) cnt += g[j-v];//使用当前物品是max，则加上方案数
g[j] = cnt % mod; //这里只在g之间转移，而没有取max这样就严格保证了是使用体积j(全用)的最大方案数
f[j] = maxv;
}
}最后先找一下
f中的最大价值是多少，再遍历f,当当前是最大价值的时候，我们对g[i]累加代码如下：
2
3
4
5
6
7
8
9
for(int i = 0; i <= m; i ++) maxv = max(maxv, f[i]);
int ans = 0;
for(int i = 0; i <= m; i ++)
if(f[i] == maxv)
ans = (ans + g[i]) % mod;
cout << ans << endl;
在前面我们做过一个题目【机器分配】，也是输出一个方案，但是不要求是方案的最小字典序。
并且求具体方案的题目大多不能使用滚动数组来优化，因为我们要在最后用到每一层的数据
上一个题目是分组背包，找方案的时候需要遍历当前分组中的所有元素，该题是01背包，则少一层循环。
上一层我们是倒着找具体方案，所以找到的不是最小字典序，这里我们需要正着来找
但是考虑到正着找的话，我们并不能使用再前面的数据，换言之当我们使用
f[i]的时候，不能使用前面的数据f[i-1]来更新，只能使用后面的数据，所以我们在前面做01背包的时候，我们从最后一个开始做。然后找方案的时候能有靠前面的满足匹配的就一定要选，这样能保证找出的方案的字典序
【能量石】
基于贪心的DP问题
假设我们以及剔除了贡献为0的宝石（最最后面吃的）
现在我们得到了可以做出贡献的宝石序列
a1,a2,a3… ak那么对于任意两个位置
交换后两个宝石的贡献总和不会变得更大，即（假设之前的总时间为tt ）：
整理后：
我们可以把跟i有关的放到一边，调整一下:
这样，我们只要以如上条件作为宝石间排序的条件，进行一次sort。
因为对于其他形式的放置规律，必然可以通过交换满足$SiLi>SjLj$的相邻的两项来得到更小值。
那么最优解的坐标（新的坐标）一定满足：
此时转化为01背包问题
f[i]表示当前正好花费t时间得到的最大值转移方程：
由于我们背包放物品（宝石）的顺序是坐标从1到n的，所以一定能枚举到最优解。
初始状态：
f[0]=0，其余为负无穷答案：$max(f[i])(1<=i<=∑ni=1si)$
公式摘选自：墨染空
下面给出我的思考：
- 前面使用贪心预处理数据，得到先后顺序
- 下面利用值域较小，可以枚举的性质，使用
f[i]表示恰好使用i的时间吃到的总能量- 吃时候的得到的能量可以通过枚举的当前时间计算而来，价格是固定的
这种类似的题目都是枚举权值的方向来思考状态表示，至于前天的贪心嘛，需要题量来积累。
【金明的预算方案】
这道题看起来有一股有依赖的背包，但是实则不然，这个依赖关系比较浅，【有依赖的背包问题】依赖关系较深
由于每个点只有最多两个子节点，而且不会有孙子结点，所以我们可以枚举当前子节点的所有可能，进而演化为一个分组背包问题。
记忆点：
- 分组背包建图时需要两个二维数组，对应付出价值和回报价值
- 分组背包没有办法使用滚动数组来优化，如果使用了会导致同一组物品多个被利用