背包问题、线性动归、多维动归、技巧与记忆化
《背包问题九讲》
背包九讲
01\完全\多重\混合
-
01（每个物品仅1个 总容量V不用装满）
for i=1..n for j=V..v[i] ans[j]=max(ans[j],ans[j-v[i]]+w[i]); -
完全（商品可多次取）
for i=1..n for j=v[i]..V //区别在此 ans[j]=max(ans[j],ans[j-v[i]+w[i]]); -
多重（有1个的有n个的）
-
混合
二维费用
2种总容量。每个物品2种费用、2种价值。用二维数组即可。
分组的背包
物品被划分为若干组。每个组之间物品相互冲突，最多选1件。
for 所有的组k
for j=V..0
for i=k里所有物品
f[j]=max(f[j],f[j-v[i]]+w[i]);
注意V层循环必须包裹i层
有依赖的背包
泛化物品
分组的背包问题
P1060 开心的金明
启蒙文章：https://www.luogu.org/blog/user21354/solution-p1060
-
一维常数优化的bound啥意思
关于一维常数优化
看了几篇文章。终于自己理解出了常数优化的意思。主要是很多文章讲得迷迷糊糊，还有的给的方程是错的。要么就是w和v这种字母乱用文章也不解释清楚代表啥就放公式！
下面我来说说自己的理解。二维的情况就不说了。先看一维优化后代码是这样的：
总容量V 每个物品容量v[i] 每个物品价值w[i]
for i=1..n
for j=V..v[i]//容量小于v[i]的肯定放不下v[i] 没必要更新
ans[j]=max{ans[j],ans[j-v[i]]+w[i]}
核心思想：
思考，是不是整个循环跑下来。我们只不过是要个ans数组的最后一个元素。
假设总容量V=20.5个商品 我们不就想要个ans[20]吗？
那i=5时，是不是执行一次更新ans[20]就好了。没必要再更新ans[19]了吧？
假设第5个物品容量v[5]=3，我们是不是只需要ans[17]这个结果就行了？
在i=4的那层循环里，假设v[4]=3,那我只需要更新到ans[17-3]即ans[14]就可以了啊。因为有了ans[14]，如果物4和5都需要被放进去。我们还有足够的6个空间放啊。
所以我们需要一个常数优化。尽可能地提高V的下界（这样更新的次数就少了）
看代码：
for i=1..n
sumV-=v[i];//i个物品总容量和为sumV，减去第i个的v[i]，就是剩下物品需要的容量和。只要更新到这里就足够后面的物品i+1到n全放进去的容量了。
bound=max(v[i],V-sumV);//v[i]和V-sumV选一个最大的即可。如果比v[i]还小，第i个肯定放不进去，ans不必更新；如果比V-sumV还小更新了后面也用不到。就像刚刚说的，第5个商品只需要看ans[17]就可以了。ans[16]是多少都无所谓啊。我ans[17]里存的数肯定比你ans[16]还大。ans[16]在后面i的循环中也不可能被用到。
for j=V..bound
ans[j]=max(ans[j],ans[j-v[i]]+w[i]);
P1064 金明的预算方案
采用分组的思路。毕竟这题附件最多两个。可以枚举出4种情况。这四种情况就是一组。
然而枚举的方法毕竟不适合附件多的情况。看看别人的解法吧！
这题的小坑：
- 附件编号是商品的总编号。由于我是分组存。要对总编号和我自己的分组编号做一个映射。
- 权重是 价格*价值。
P1164** 小A点菜
-
重刷标记！
P1048 采药和P1616 疯狂的采药
采药就是基本的0-1背包。而疯狂的采药则是完全背包。
下面先看一下他们dp遍历的过程：
都采用一维数组优化，
输入数据为：容量m=20 物品数量n=3
分别是 ①v=50,w=100 ②v=15,w=1 ③v=1,w=2
第一个商品一定放不进去。我们不做讨论。主要看2、3
-
0-1背包:容量m从20开始，循环条件m>=v[i].
-
i=2时，ans[20]~ans[15]都更新了。ans[14]循环停止。
-
i=3时，ans[20]=max(1,ans[20-1]+2)
就是容量为19时的最大值1，加上第三个物品，更新最大值3
-
-
完全背包:m从0开始到到20。
- i=2时，一直到ans[15]才能放进去。
划重点 看下面
-
i=3时,ans[1]=2, ans[2]=max(0,
ans[1]+2)=max(0,4)=4看到没,容量为2时，最大值是容量为1时的，再放进去一个③。③被放了两次。这就是完全背包问题。
记得用一维数组做。用二维的是
ans[i][j]=ans[i-1]xxx，从状态转移方程上就限定了，第i个物品不会被多次存入。
P1049 装箱问题
水题。
线性动归
P1020 导弹拦截
最长不升序列和最短上升序列
好题！
需要注意的是lower/upper_bound这个方法:
- 必须传入有序的数列，且根据排序规则传入一个compare方法
- 返回值是一个指针，故
-vt.begin()得到的是数组下标，为什么会得到？肯定是因为重载了-
实例：
vector<int> vt = {1,2,2,2,3,4,5,6,7};
auto p1 = lower_bound(vt.begin(),vt.end(),2)-vt.begin();//1 第一个2
auto p2 = upper_bound(vt.begin(),vt.end(),2)-vt.begin();//4 3的位置
//下面vt改成降序
vt = {7,6,6,6,5,4,3,2,1};
//最后传入的比较函数也应改成greater<int>()
auto p3 = lower_bound(vt.begin(),vt.end(),6,greater<int>())-vt.begin();
auto p4 = upper_bound(vt.begin(),vt.end(),6,greater<int>())-vt.begin();
可以理解为：在有序序列中插入一个元素a，lower_bound返回的是能插入的最小的坐标，upper返回的是最大的坐标。