动态规划之三维01背包问题

动态规划问题是学习算法时一个尤为重要的内容，在讲解什么是动态规划之前，首先来讲一下分而治之。

分而治之就是一个大问题可以被分解成许多个小问题，逐个解决最后合并即可。归并排序就是使用的分而治之，时间复杂度为O(n*logn)，空间复杂度O(n)。但是我们在使用归并排序时，每个子问题都是只被计算一次，但是如果每个子问题不相互独立，需要被重复计算好多次，分而治之就不再是明智的选择了，完全可以把子问题的结果放在一个表中，需要就直接去查即可，这种存放子问题结果的方式就是所谓的动态规划。

动态规划可以解决各种问题，比如矩阵连乘（最小连乘次数），最长公共子序列，01背包……

今天我们用动态规划解决三维01背包问题，在解决三维01背包之前，简单的讲一下01背包问题：有一个背包，最大载重W，有n个物品，每个物品重量为w[i]，价值为v[i]，1 <= i <= n，i是整数。装入哪些物品才能使装入物品的总价值最大？下面给出01背包问题的动态规划解决思路，代码就不实现了，因为今天要解决的问题不是这个，但是今天要解决的问题是建立在这个问题的基础上。

阶段：在前N件物品中，选取若干件物品放入背包中；

状态：在前N件物品中，选取若干件物品放入所剩空间为W的背包中的所能获得的最大价值；

决策：第N件物品放或者不放；

由此可以写出动态转移方程：

我们用f[i, j]表示在前i件物品中选择若干件放在所剩空间为j的背包里所能获得的最大价值

f[i, j] = max{f[i-1, j-w[i]]+v[i](j >= Wi), f[i-1, j]}

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

在这个问题中，仅仅只有一个限制条件，也就是最大载重，可是有些时候背包并不只是载重受限，体积也会受限，当01背包问题有两个限制条件：载重和体积，这样01背包问题就变成了三维01背包问题。（这是我上网查的三维01背包问题的定义，不知道对不对，敬请谅解）同样的也可以写出动态转移方程：f[i, j, k] = max{f[i-1, j-w[i], k-V[i]]+v[i](j >= w[i], k >= V[i]), f[i-1, j, k]}，V[i]表示第i个物品的体积，k表示剩余体积。

下面来看一下代码的实现和运行结果，为了方便大家理解，做了一些输出并且代码中有注释。

如果大家想知道具体的规划过程，解开上面代码的多行注释然后运行即可。