背包DP

背包问题一般表现为这样的形式:有 \(N\) 件物品和一个容量为 \(V\) 的背包,选取第 \(i\) 件物品耗费 \(C_i\) 的空间,得到 \(W_i\) 的价值,问怎样使背包总价值最大。

01背包

每种物品只有一件,所以只有取或不取两种选择。

容易设计出这样的状态:\(dp[i][j]\) 表示只用前 \(i\) 件物品装入容量为 \(j\) 的背包的最大价值。在枚举到 \(dp[i][j]\) 的时候,如果我们选了这个物品,就需要为它预留下至少 \(C[i]\) 的空间,所以要从上一轮找到背包大小为 \(j - C[i]\) 时的最大价值,再和 \(W[i]\) 相加;如果我们不选,那就相当于求前 \(i-1\) 个物品装入大小为 \(j\) 的背包的最大价值,即 \(dp[i-1][j]\)。

于是我们得到了这样的状态转移方程:\(dp[i][j]=\max(dp[i-1][j],dp[i-1][j-C[i]]+W[i])\),对应不取和取两种选择。

这种做法的时空复杂度都是 \(O(NV)\),时间复杂度已经没办法优化了,空间复杂度可以进一步优化:

由于每一轮的状态都只从上一轮转移过来,再之前的状态都没用了,没有必要保存,所以空间复杂度可以优化到 \(O(V)\)。但是要注意,我们不能直接用 \(dp[i][j]\) 刷新 \(dp[i-1][j]\),因为 \(dp[i-1][j]\) 以后还可能转移到 \(dp[i][j+C[i]]\),但是从大到小更新 \(j\) 就不会出问题。

还有一个常见的问题是尽可能装满背包,其实只需初始化的时候把 \(dp[0]\) 之外的都赋值为 \(-\infty\)。这样就确保了最后有意义的状态都是从 \(dp[0]\) 处转移过来的。

完全背包

所有物品数量无限。

首先容易想到转化为01背包问题:

暴力转化:每种物品最多选 \(\dfrac{V}{C}\) 件,那就把它们分别复制这么多份,这就转化成了01背包问题,时间复杂度 \(O(NV\sum\dfrac{V}{C_i})\)。

二进制优化:将 \(\dfrac{V}{C}\) 拆成 \(2\) 的幂次和,同样能组合出所有可行的数量,时间复杂度 \(O(NV\sum\log\dfrac{V}{C_i})\)。

能不能优化到 \(O(NV)\)?现在 \(dp[i][j]\) 依然表示只用前 \(i\) 件物品装入容量为 \(j\) 的背包的最大价值。再来看状态转移方程,由于所有物品无限,有 \(dp[i][j]=\max(dp[i-1][j],dp[i][j-C[i]]+W[i])\)。为什么是 \(dp[i][j-C[i]]+W[i]\)?01背包需要保证每件物品最多选一次,如果选的话就必须从上一轮转移,因为上一轮的最优解必不可能包含这一轮的物品;完全背包恰恰相反,要从可能已经选过该物品的状态转移过来,所以从当前轮次转移。那么在实现的时候只需要把01背包的内层循环改为从小到大更新即可。

多重背包

第 \(i\) 种物品最多可选 \(M_i\) 件。

经典的做法是利用完全背包的二进制优化做法。

那么能不能也优化到 \(O(NV)\) 呢?先来观察一下没有任何优化的状态转移方程:

\[dp[i][j]=\max \lbrace dp[i-1][j-k\times v_i]+k\times w_i\rbrace,k\in [0,M_i] \]

我们的目标是设计 \(O(NV)\) 的算法,就是要把 \(i-1 \to i\) 的转移从 \(O(VM_i)\) 优化到 \(O(V)\)。令 \(f(x)=dp[i-1][x]\),\(k=\dfrac{V}{v}\) 则有

\[dp[i][V] = \max(f(V),f(V-v)+w,f(V-2v)+2w,\cdots ,f(V-kv)+kw)\\ dp[i][V-v] = \max(f(V-v),f(V-2v)+w,f(V-3v)+2w,\cdots ,f(V-(k-1)v)+(k-1)w)\\ \cdots \]

那么将 \(dp[i][V-tv]\) 式子两边都减去对应的 \((k-t)w\),就变成了:

\[dp[i][V]-kw=\max(f(V)-kw,f(V-v)-(k-1)w,\cdots ,f(V-kw))\\ dp[i][V-v]-(k-1)w=\max(f(V-v)-(k-1)w,f(V-2v)-(k-2)w,\cdots ,f(V-(k-1)w))\\ \cdots \]

这样看来,只有所有对 \(v\) 取模余数相同的 \(j\) 才会互相影响,并且上面这个转移明显可以用单调队列优化。现在重新写一下状态转移方程:令 \(a=\dfrac{j}{v},b=j\mod v\),即 \(j=av+b\),那么 \(j-kd=(a-k)v+b\)(这里的 \(k\) 就是上面的 \(k-t\)),得到

\[dp[i][j]=\max\lbrace dp[i-1][(a-k)v+b]-(a-k)w+aw \rbrace \]

所以把 \(dp[i-1][(a-k)v+b]-(a-k)w\) 放进单调队列就好了。

混合背包

根据物品所属的背包问题类别使用相应的方法求解。

分组背包

所有物品被分为 \(K\) 组,每组最多选一件。

类似于01背包,用 \(dp[k][v]\) 表示只用前 \(k\) 组的物品装入容量为 \(v\) 的背包的最大价值。

二维费用

背包和物品均具有两种费用。

那么只要加一维状态就好了。

树上背包

物品之间的依赖关系以一棵有根树的形式呈现,如果要选某个结点就需要选择它的全部祖先。

一般这样设计状态:\(dp[u][i][j]\) 表示当前结点 \(u\) 计算到前 \(i\) 个子树装入大小为 \(j\) 的背包的最大价值。假设 \(u\) 的第 \(i\) 个儿子是 \(v\),\(v\) 有 \(n_v\) 个儿子,那么 \(dp[u][i][j]=\max(dp[u][i-1][j],dp[v][n_v][k]+dp[u][i-1][j-k])\)。和01背包一样,我们可以倒序枚举 \(j\),省掉一维空间。显然,时间复杂度 \(O(NV^2)\),空间复杂度 \(O(NV)\)。

树上背包问题的时间复杂度也能优化到 \(O(NV)\),但是比较复杂。

上一篇:数据结构 图10.16被Gank的亚索 代码存放


下一篇:量子精密测量技术大突破,应用正当时,国仪量子成果斐然