背包问题、线性动归、多维动归、技巧与记忆化
《背包问题九讲》

背包九讲

01\完全\多重\混合

01（每个物品仅1个总容量V不用装满）

1
2
3

for i=1..n
  	for j=V..v[i]
  			ans[j]=max(ans[j],ans[j-v[i]]+w[i]);

完全（商品可多次取）

1
2
3

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]

1
2
3

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返回的是最大的坐标。

多维动归

技巧与记忆化

Adopting CC BY-NC-SA 4.0 License Agreement

洛谷4-动归专题