背包问题
什么是背包问题
现在有一个背包,容量(Capacity)为$C$,有一堆物品,这些物品有重量(Weight)和价值(Value)两种属性,背包中所有物品的重量之和$\sum{item_{Weight}}$不能超过$C$,问:背包中最多可以装价值总和为多少的物品?
0-1背包问题的数学表示?
给定待选取物品的属性表示:${({w_i, v_i})}_{i\in[1,n] }$,给定背包容量$C$,OK,可以开始动态规划啦!
0-1背包问题的递推关系
假设我们求解0-1背包问题的函数为$knapsack(the\ set\ of\ items,\ capacity\ of\ the\ sack)$,那么该函数的功能就是:按属性给定所有物品,以及背包容量,求解可获得的(物品价值)最大值。
为了方便,以下我们将以上函数略写为$K(i,\ C)$,而此时问题的解为$Opt(i,\ C)$。
那么对于所有物品中的第$i$个,只有两种选择:
放进背包
如果把当前物品放入背包,那么这个选择带来的后果是:背包总价值增加,背包可用容量减少,当前物品不能再次选择,接着我们可以进入下一件物品的抉择:$K(i-1,\ C-W_i)$。这里我们注意一下,之所以是$i-1$,是因为我们是从后向前的顺序选择物品。
不放进背包,并开始下一件物品的选择
如果物品不放进背包,可能的原因就是当前背包剩余空间不足,必须跳过这件物品去对下一个物品进行选择,那么此时的问题就变为$K(i-1,\ C)$。
那么针对这第$i$件物品的两种选择,产生了两种方案,哪一种是更优的方案?于是我们对“更优”的标准的判定指标:背包内物品总价值,进行比较,进而选出两种方案中更优的方案,即:$Opt(i,\ C)=max(Opt(i-1,\ C-W_i)+V_i,\ Opt(i-1,\ C))$。
对这个函数进行递归调用,直到没有物品可选。用文字来描述整个递归的过程:对于当前物品,如何选择拿还是不拿?要根据两种选择的结果选最优。
动态规划
动态规划的核心
动态规划的核心是保存已经解决过的子问题。
动态规划的两种形式
用求解斐波那契数列之和的问题作为例子,我们之前在学习递归方法的时候出现过这个例子。很容易想到在求解过程中,由于状态转移表达式为$f(n)=f(n-1)+f(n-2)$,会出现很多重复求解。
- 自上而下的备忘录法
创建一个表来记录已经求解过的值,每次递归计算之前先查表; - 自下而上
不用递归,从子问题开始计算最后计算父问题。
“填表”的动态规划方法
对于下表中的物品列表:
Item | Value | Weight |
---|---|---|
1 | 1 | 1 |
2 | 6 | 2 |
3 | 18 | 5 |
要填的二维表如下:
当前物品列表序号表示 \ 背包容量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
{} | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
{1} | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
{1, 2} | 0 | 1 | 6 | 7 | 7 | 7 | 7 | 7 | 7 |
{1, 2, 3} | 0 | 1 | 6 | 6 | 6 | 6 | 6 | 24 | 25 |
表格中每个空白的格子都表示$K(i,\ C)$所有不同输入参数时的解,比如我们现在的背包容量$C=8$,那么我们要填的格子就是$({1,2,3},8)$这一格,为了填上这个格子我们需要从左上角开始填,第一行由于没有物品可选因此全0。从第二行开始,对于$item1$,$C\geq W_1$即$C\geq 1$的格子可以放得下,因此从[1, 1]
这一格开始判断,比较$Opt(0,\ 1)$和$Opt(0,\ 0)+V_1$,那么通过查表很容易知道是后者比较大且为1,那么在这一格填上1。
我们很容易看出来,这就是自下而上的动态规划,从头开始计算,从子问题开始计算,而每计算一个格子的内容都需要以这个格子为右下角元素的表格的内容。在这个问题中,当我们计算到最后时,需要比较$Opt(2,\ 8)$和$Opt(2,\ 3)+V_3$,那么很明显是后者大,于是我们的结果即为后者,直接由表格中数据计算而来。
以上这种动态规划方法并不需要递归,而是只要用一个表格即可解决,那么可想而知空间复杂度为$O(num\ of\ itemsC)$,而由于算法需要遍历这个表格,因此时间复杂度则也是$O(num\ of\ itemsC)$。
“填表法”的优化
以上填表法的动态规划中,我们其实浪费了很多空间,因为在计算最终结果的过程中根本没有用到这些位置存放的值,而且计算第n行的数据只需要第n-1行的数据,因此我们只需保存两行数据即可。
如此,我们的空间复杂度被优化为$O(C)$,时间复杂度不变。
2020/6/10 更新
这里主要总结一下动态规划套路,参考https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/dong-tai-gui-hua-xiang-jie-jin-jie。
首先,动态规划的一般形式就是求最值,最长子字串、最长子序列、最短距离等等
要求最值,核心问题是穷举,不穷举我们怎么知道我们找到了最优解(除非可以证明,那么这个时候贪心就可以)
穷举的过程中有重叠子问题
存在最优子结构,原问题最优解可以通过子问题的最优解得到
如何写出状态转移方程?
明确base case -> 明确状态变量 ->明确选择->定义动态规划数组/函数的意义
框架:
1
2
3
4
5
6
7# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值:
for 状态2 in 状态2的所有取值:
for ...
dp[状态1][状态2][...] = 求最值(选择1,选择2...)
最优子结构
要满足最优子结构,各个子问题之间一定需要相互独立。
动态规划的必要条件是满足最优子结构,也就是说动态规划能解决的问题都有最优子结构,而最优子结构一般都是求最值,所以求最值都能用动态规划解。
如何一步一步优化到动态规划
从暴力法开始:如何用递归解决问题?
是否有重复子问题?有的话记忆化递归。
状态是否可以压缩?可以的话就用迭代写。