简单来说,此问题基于“二维0-1背包”。在二维中,我们需要考虑背包的价值,背包的重量。“三维0-1背包”增加了“体积”这一维度。要弄清楚此问题,不妨先复习下DP方法解决二维0/1背包的思路。

二维,不考虑体积

构建子问题

我们从头开始,假设现在背包中放入的物品的价值最优,在考虑下一个物品时,则只需要考虑「放入」与「不放入」。
我们用 f[i, j] 表示在前 i 件物品(即物品编号为1~n)中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值,于是就有以下

状态转移方程:

f[i,j]={max{f[i1,jw[i]]+v[i],f[i1,j]}(jWi)f[i1,j](0jWi)f[i,j] = \left\{\begin{matrix}max\left \{ {f[i-1, j-w[i]]+v[i] , f[i-1, j]}\right \} _{(j \ge W_{i})}\\f[i-1, j]_{(0 \le j \le W_{i})}\end{matrix}\right.

这样,我们可以自底向上地得出在前N件物品中取出若干件放进背包能获得的最大价值。

三维

构建子问题

和二维相同,在考虑下一个物品时,则只需要考虑「放入」与「不放入」。
我们用 f[i,j,k] 表示在前 i 件物品(即物品编号为1~n)中选择若干件放在所剩空间为 j ,所剩载重为 k 的背包里所能获得的最大价值,于是就有以下

状态转移方程:

f[i,j,k]={max{f[i1,jw[i],kb[i]]+v[i],f[i1,j,k]}(j>=w[i],k>=b[i])f[i1,j,k](0jWi0jWi)f[i, j, k] =\left\{\begin{matrix}max\left \{f[i-1, j-w[i], k-b[i]]+v[i], f[i-1, j, k]\right \}_{(j >= w[i], k >= b[i])}\\ f[i-1, j ,k]_{(0 \le j \le W_{i} || 0 \le j \le W_{i})}\end{matrix}\right.

只在二维基础增加一维,其余完全不变。

实现形式

根据上面的公式,初始化表格(f[1,w[0],b[0]]=v[0]i=0j=0k=0情况置0)。并将 i,j,k嵌套循环。
此时这个三维表格即可填满,f[n,c,d]即为最大价值。(所有物品n,包最大重c,最大容量d)
然后自顶向下,找出f[i-1, j-w[i], k-b[i]]+v[i]f[i-1, j, k] 中更大的值,若是前者,则证明当前第 i 件物品已装入;若是后者则未装入。

复杂度

该算法需要填一张三维表格,需要 O(ncd)O(ncd) 时间,回溯表格需要 O(n) 时间。总共为 O(n+ncd)=O(ncd)O(n+ncd) = O(ncd)时间复杂度。