前言
背包问题一直是DP的经典模型,但是像我这样的菜鸡总是学不会 (再聪明一点) 所以综合之前的做题和听课,把自己的一点感悟记录下来。(大部分与背包九讲一致)
01背包
01背包是背包模型的基础,也是我DP入门的噩梦,那就从这个问题入手吧。
题目
N件物品和一个容量为V的背包,每件物品有一个体积为c,有一个价值为v。求解背包能装入最大的价值总和。
思路
状态表示: \(f[i][j]\) 表示前i件物品放入容量为j的背包所能获得的最大价值和
状态计算:
- 状态转移方程: \(f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+v[i])\)
- 初始状态: \(f[i][0]=0,f[0][j]=0\)
- 边界条件: \(j<c[i]\) 时, \(f[i][j]=f[i-1][j]\)
代码
1 | //初始状态由于定义全局变量默认为零故不用设置 |
空间复杂度优化
此处的优化方法主要是观察代码与状态转移方程得出的。注意到状态转移方程中 \(f[i][j]\) 仅由 \(f[i-1][j]\) 与 \(f[i-1][j-c[i]]+w[i]\) 决定,故将第一维删去,得代码1:
1 | for(int i = 1; i <= N; i ++) |
代码1存在两点问题
- 问题1:边界状态为恒等式,删去
- 问题2:考虑 \(i=I,j=J\) 时,此时由于内层循环是从小到大的顺序去更新,所以 \(f[J-c[I]]\) 在 \(f[J]\) 之前被 \(c[I]\) 更新了,也就是说,此时的 \(f[J-c[I]]\) 等价于二维中的 \(f[I][J-c[I]]\) 而非 \(f[I-1][J-c[I]]\) ,所以内层循环应当从大至小,又考虑边界状态,终止条件就是 \(j>=c[i]\)
更改后得一维的01背包代码:
1 | for(int i = 1; i <= N; i ++) |
装满问题
原题设意指背包不一定装满,若要求装满,则需要将除 \(f[0]\) 外所有 \(f[j]\) 设为 \(-\infty\)
从题意角度解释,就是空间为0的背包始终视作是装满的。
也可以手算模拟,看内层循环, \(i=1\) 时,仅有 \(f[c[i]]=w[i]\) ,其余仍为负无穷。可以推断外层循环结束后,此时只要非负即可视作对于容量为 \(j\) 的背包装满。
完全背包问题
题目
一个容量为V的背包,N类物品,每类都有无限个,每个物品有一个体积为c,有一个价值为v。求解背包能装入最大的价值总和。
思路
状态表示: \(f[i][j]\) 表示前i类物品每类挑选任意个放入容量为j的背包所能获得的最大价值和
状态计算:
- 状态转移方程: \(f[i][j]=max(f[i-1][j-k*c[i]]+k*v[i]),k\in[0,\lfloor\tfrac{V}{c[i]}\rfloor]\)
- 初始状态: \(f[i][0]=0,f[0][j]=0\)
- 边界条件: \(j<c[i]\) 时, \(f[i][j]=f[i-1][j]\)
代码
1 | for(int i = 1; i <= N; i ++) |
搜索剪枝
若物品i、j满足 \(c[i]<c[j]\) 且 \(w[i]>w[j]\) ,则可以忽略物品j。该优化不能改变最坏复杂度。
降维优化
展开 \(f[i][j],f[i][j-c[i]]\) 的状态转移方程观察:
\(f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+v[i],f[i-1][j-2*c[i]]+2*v[i]...f[i-1][j-k*c[i]]+k*v[i])\)
\(f[i][j-c[i]]=max(f[i-1][j-c[i]],f[i-1][j-2*c[i]]+v[i]...f[i-1][j-k*c[i]]+(k-1)*v[i])\)
得结果 \(f[i][j]=max(f[i-1][j],f[i][j-c[i]]+v[i])\)
利用滚动数组降维,对比01背包的方程和优化知,由于此处转移方程含 \(f[i][j-c[i]]\) 所以内层循环变量j应该从小到大循环,使得 \(f[i-1][j-c[i]]\) 被更新为 \(f[i][j-c[i]]\) 进而更新 \(f[i][j]\)
二进制优化
二进制优化,在多重背包内细讲
代码
1 | for(int i = 1; i <= N; i ++) |
对比01背包的代码,可以发现二者差别仅在内层循环,一个是从小到大,一个是从大到小,从状态和阶段的角度去解释,就是01背包当前状态是由上一阶段( \(i-1\) )的状态转移而来的,而完全背包的当前状态是由当前阶段已经被更新的状态( \(i\) )(体现出一类物品有无数个)和上一阶段( \(i-1\) )的状态转移而来的。
所以,因为阶段仅涉及当前和 前一个状态 所以可以使用滚动数组去优化空间
多重背包问题
题目
有 N 种物品和一个容量是V的背包,第i种物品最多有 \(c_i\) 件,每件体积是 \(v_i\) ,价值是 \(w_i\) 。求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
思路
状态表示: \(f[i][j]\) 表示前i类物品每类挑选不大于 \(s[i]\) 个放入容量为j的背包所能获得的最大价值和
状态计算:
- 状态转移方程: \(f[i][j]=max(f[i-1][j-k*c[i]]+k*v[i]),k\in[0,s[i]]\)
- 初始状态: \(f[i][0]=0,f[0][j]=0\)
- 边界条件: \(j<c[i]\) 时, \(f[i][j]=f[i-1][j]\)
代码
1 | for(int i = 1; i <= N; i ++) |
二进制优化
所谓的二进制优化,实质上是把多重背包转换成了01背包,转换时使用到二进制。
显然的,每一个十进制整数都可以表示成二进制形式,写成按位权和展开的形式。考虑第 \(i\) 类物品,对于 \(c[i]\) 个物品,我们将 \(c[i]\) 表示成 \(c[i]=a_0*2^0+a_1*2^1+a_2*2^2+...+a_k*2^k+C,a_i=0或1\) ,也就是说将 \(c[i]\) 件物品拆分,并按照 \(1,2,4,8,16...2^k\) 组合成新的一类物品。对于新的第 \(i\) 个物品, \(a_i=0\) 是不取,反之为取。通过这样的操作,实质上我们可以组合出取任意件第 \(i\) 类物品的情况。对于所有的物品进行此项操作后,问题转换成01背包
1 |
|
单调队列优化
由于本篇标题为背包基础,所以在这里就不深入阐述了,大概会再发一篇背包进阶来阐述这一部分以及其他类型的背包。(咕咕咕咕咕
练习题
传送门->Warma的硬币