背包问题

浩浩荡荡开始DP了,然后自己背包还是一团糟==当时就想着过一阵子在搞结果就是半年(TB:都这时候了还不如AFO算啦)qwq
这次再温习背包决定比较深入的扩展一下,形式模拟《背包九讲》。
千里DP,始于背包。

01背包

问题不用描述了。
设f[i][j]为前i个物品取0~1个放入容量为j的背包的最大价值,w[i],c[i]为第i个物品的体积和价值,我们可以直接得到转移方程:
$$f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i])$$
这样两层for循环直接求解就可以了。
但发现空间其实可以更优化。因为当前所有f[i]的计算只用用到先前计算的f[i]和f[i-1],数组滚动一下就办到了。
时间上一有个常数优化,第二层循环原来为for(int i=V;i>=w[i];i–),边界w[i]其实可以改为$$max(w[i],\sum_{t=i}^n w[t])\tag{想一想,为什么}$$

完全背包

递推式同样显然
$$f[i][j]=max(f[i-1][j],f[i][j-w[i]]+c[i])$$
唯一的不同就在第二个f[i-1]变成了f[i],这就保证了某个物品可以多次被选。
实现改变一下01bag的循环次序就可以了。

多重背包

也是首先写出递推式
$$f[i][j]=max(f[i][j-k×w[i]]+k×c[i]) (0≤k≤lim[i])$$
可以直接求出每个物品最大使用量变成01背包,加上一个简单有效的优化就是把最大使用量拆成2的幂次形式,如38=1+2+4+8+16+1+2+4,用这些数,就可以凑出0~38所有数了,也是一个01bag.
这样下来,时间复杂度就可达到O(n×V×log w[i])
其实可以使用DP中常用的单调队列优化来去掉后面那个log(事实上,很多题目中也不会给log生存空间)
怎么做呢,首先要了解下什么是单调队列和它的基础运用,找了一个网上讲的最清楚的《用单调性优化动态规划》
传送门 >>http://wenku.baidu.com/view/83e4fec59ec3d5bbfd0a74e1.html
优化的结果,就是我们要O(1)算出f[i][j]的值,设a=j/w[i],b=j%w[i],即j=a×w[i]+b,递推式可转化为f[i][j]=max(f[i][k×w[i]+b]+(a-k)×c[i])=max(f[i][k×w[i]+b]-k×w[i])+a×wi
对于相同i中b相同的j,将f[i][k×w[i]+b]-k×w[i]推入deque,O(1)询问就可以辣~
这样做到将复杂度降到O(n×V)

混合背包

for的时候判断是什么类型的物品再分类求解即可。

二维费用背包

其实跟一维原理是一样的,方程就不再赘述,也有01,完全,多重,也可拓展到多维,都应该是很简单的。
什么鬼复整数域解二维背包,没有查到相关资料,就弃疗了。
反思:在平常出题过程中,增加一维限制是很常见的,所以要拨开表象看到本质,简化问题。

分组背包

01背包中,把第一二层循环次序交换,就可得到只装一个物品的最优值(想一想,为什么)。
然后对多组背包进行这样的操作即可。

依赖背包

将每个主件和其的附件分别进行一次背包,这样得到了这个组合的一系列最优方案,可以把他们看成多个物品组,最后将所有物品组放在一起背包即可。
所有物品形成一个依赖森林,这样做下去,也就是树形DP了,即“在用动态规划求每个父节点的属性之前,需要对它的各个儿子的属性进行一次动态规划式的求值”。

泛化物品

泛化物品,也就是价值随着费用改变的物品,也是一个定义在非负整数域的函数。
单个物品是一个泛化物品,如01背包中的物品,当费用给值w的时候,价值为c,其他费用时都为0;完全背包中的物品,当费用给值k w时,价值为k c,其他费用均为0。
泛化物品求和也是一个泛化物品,如整个01背包,在给的容量不同的情况下,最优价值也不用。
这些都是特殊的泛化物品,但价值随费用的变化遵循一个函数f(x)的时候,要如何计算呢?
最基础的方法,我们可以计算两个泛化物品的和,设a物品遵循g(x),b物品遵循h(x),我们通过简单的可以简单的枚举求得,设总费用为V,答案即为max{g(t)+h(k-t)} (0≤t≤k≤V),通过两层循环枚举k,t的值即可,这样我们就可以用$O(V^{2})$的时间算出来了。这样我们得到一个新的泛化物品,就可以继续与其他物品求解了。
我们发现,背包问题事实上也就是很多泛化物品求和。

背包问题的扩展

有时候背包问题考得很灵活。
下面是两个简单的问法:
· 求解最多可以放多少件物品
· 求解最多可以装满多少背包的空间
只要理解了背包问题最大价值的求法,应该是不难脑补的。
再想一想要求放满背包的最小价值和最少放多少件物品。

下面说一些变化更大的问法。
· 输出方案
像动态规划的一般问题,方程转移的时候记录下转移方向就可以了。
· 输出字典序最大的最优方案
就是在输出方案的时候注意一下,若两个转移项相等的时候,选择字典序更大的那个就可以了。
· 最优方案总数
另设一个数组g[x][y],随f一起转移就可以了:

1
2
3
4
5
6
g[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=V;j>=w[i];j--)
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]+c[i]])
if(f[i][j]==f[i-1][j]) g[i][j]+=g[i-1][j];;
if(f[i][j]==f[i-1][j-w[i]]+c[i]) g[i][j]+=g[i-1][j-w[i]]

· 次优解、第K优解
懒得写了,摘抄一段

对于求次优解、第K优解类的问题,如果相应的最优解问题能写出状态转移方程、用动态规划解决,那么求次优解往往可以相同的复杂度解决,第K优解则比求最优解的复杂度上多一个系数K。其基本思想是,将每个状态都表示成有序队列,将状态转移方程中的max/min转化成有序队列的合并。
这里仍然以01背包为例讲解一下。 首先看01背包求最优解的状态转移方程: F [i, v] = max{F [i − 1, v], F [i−1, v − Ci] + Wi}。如果要求第K优解,那么状态F [i, v]就应该是一个大小为K的队列F [i, v, 1 . . .K]。其中F [i, v, k]表示前i个物品中,背包大小为v时,第k优解的值。这里也可以简单地理解为在原来的方程中加了一维来表示结果的优先次序。显然f[i, v, 1 . . . K]这K个数是由大到小排列的,所以它可看作是一个有序队列。 然后原方程就可以解释为: F [i, v]这个有序队列是由F [i − 1, v]和F [i − 1,v −Ci] + Wi这两个有序队列合并得到的。前者F [i − 1][V ]即F [i − 1, v, 1 . . . K],后者F [i − 1,v − Ci] + Wi则理解为在F [i − 1,v − Ci, 1 . . . K]的每个数上加上Wi后得到的有序队列。合并这两个有序队列并将结果的前K项储存到f[i, v, 1 . . . K]中的 复 杂 度是O(K)。 最 后 的 第K优 解 的 答 案 是F [N, V, K]。 总 的 时 间 复 杂 度是O(VNK)。为什么这个方法正确呢?实际上,一个正确的状态转移方程的求解过程遍历了所有可用的策略,也就覆盖了问题的所有方案。只不过由于是求最优解,所以其它在任何一个策略上达不到最优的方案都被忽略了。如果把每个状态表示成一个大小为K的数组,并在这个数组中有序地保存该状态可取到的前K个最优值。那么,对于任两个状态的max运算等价于两个由大到小的有序队列的合并。
另外还要注意题目对于“第K优解”的定义,是要求将策略不同但权值相同的两个方案是看作同一个解还是不同的解。如果是前者,则维护有序队列时要保证队列里的数没有重复的。

总结

本文的重点:DP思想,状态方程转移原理,单调队列对DP的优化,DP本身的优化等。
这样,基础背包问题就愉快地结束了,打好这个的基础,DP学的应该要流畅一些吧er!