class="markdown_views prism-atom-one-light">

1 引言

1.1 背景

在许多算法中都有子程序重复计算的问题。在 Fibi 计算中采用的存储前面几个结果数值的方法并不是很通用。这样， 在很多情况下存储中间结果全列表的方法就非常有用了。
这种存储子程序结果列表的算法设计方法就称为动态规划(dynamic programming)。
——《数据结构与算法分析(C++版)(第三版)》

Fibi 指的是书中使用循环实现的斐波那契数列代码，如下： long Fibi(int n){ // Fibi(46) is largest value that fits in a long Assert((n > 0) && (n < 47), "Input out of range"); long past, prev, curr; past = prev = curr = 1; for(int i = 3; i <= n; i++){ past = prev; // past holds Fibi(n-2) prev = curr; // prev holds Fibi(n-1) curr = past + prev; // curr holds Fibi(n) } return curr; } 友情链接：(转)《剑指offer》中的斐波那契数列系列问题

2.2 动态规划问题的性质

任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。
—— 百度百科词条“动态规划”

动态规划解决的是优化问题，企图通过将问题划分成一个个子问题进而求取最优解，所以要求子问题的解是必须是最优的。同时，由于子问题一般带有重叠性，也就是带有重复计算的特点，所以我们希望保存中间结果来消除冗余计算。本质上，动态优化是一种空间换取时间的算法。 使用暴力解法求解优化问题的过程中，我们需要遍历问题的状态空间，开销很大；使用进化算法，如遗传算法时，种群的进化带有随机性，尽管理论上我们最终会获得最优解，但是解决诸如陷入局部最优、调参等问题时，我们耗费的精力也是很可观的。

2 背包问题

背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。
也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？它是在1978年由Merkel和Hellman提出的。
——百度百科词条“背包问题”

2.1 01背包

01背包问题中每种物品只有1个，物品只有两种状态，要么在背包内，要么不在背包内。 先给出状态转移方程，之后进行分析：
$P[i][j] = max(P[i-1][j], P[i-1][j-Vol[i]] + Value[i])$ 其中，$i$ 表示第 $i$ 个物体，$j$ 表示背包的容量，$Vol[i]$表示第 $i$ 个物体的体积， $Value[i]$ 表示第 $i$ 个物体的价值。 $P[i][j]$ 表示对于容量为 $j$ 的背包来说，前 $i$ 件物体放置可以得到的最大价值。（重要）

2.1.1 分析

正如我们在引言中提到动态规划的概念，在搜索空间中搜索最优解的过程中，我们将问题划分成一个个子问题，我们会不断地尝试、计算、回退，重复计算的开销很大，所以我们需要保存中间结果，这就是我们使用矩阵 $P[i][j]$ 的原因。 那么怎么决定每一个子问题最优解 $P[i][j]$ 的取值呢？状态转移方程是怎么得到的呢？ 举个例子，求容量为 10 的背包的最佳放置方案。 假如我们已经决定了前 $i-1$ 件物品的最优方案，得到了 $P[i-1][10]$ 的取值，这个值可能是 100（随便假设的），接下来我们要考虑第 $i$ 件物品了，第 $i$ 件物品的价值是 2（也是随便假设的）。 若第 $i$ 个物体在背包里，$P[i][10]$ 的取值肯定不小于 $P[i-1][10]$，为什么？因为如果将第 $i$ 件物品放进入背包，但取值反而减小了，说明有一些物品为了给物品 $i$ 腾位置被拿出来了。这才会导致取值不增反减，也会使得我们的假设不成立。 所以，我们需要考察放入物品 $i$ 后的取值能否大于 $P[i-1][10]$，否则就没有更新的必要了。 我们希望放入物品 $i$ 后的方案是最优的，不妨这样考虑：第 $i$ 个物体我们已经假设在背包里了，那么我们留下的空间只有 $10-Vol[i]$，若能找到这 $10-Vol[i]$ 的空间的最优值，在这个最优值的基础上加上物品 $i$ 的价值，不就是我们想要考察的$P[i][10]$ 的最优取值吗？（当然，是不是最优还要和 $P[i-1][10]$ 比较一番～） 而我们的矩阵正是保存着这样的最优值，注意到这 $10-Vol[i]$ 的空间只能留给前 $i-1$ 个物体，也就是说我们实际上考察的是 $(P[i-1][10-Vol[i]] + Value[i])$ 的取值能不能大于 $P[i-1][10]$。 假如我们运气好，找到的 $P[i-1][10-Vol[i]]$ 为99，那么毫无疑问，$P[i][10]$ 可以更新为 $99+2 =101$ 了。 将我们的例子泛化为一般形式就能得到状态转移方程了。

2.1.2 解决方案

假设 n 表示物体个数，v 表示背包容量。 常见的解决方案有两种，一种就是使用递归，状态转移方程实际上也是递归的递推公式，代码如下： private static int[] value; // 价值数组 private static int[] volume; // 体积数组 private static int KnapsackCore(int n, int v) { if (n < 0 || v < volume[n]) return 0; int temp1 = KnapsackCore(n - 1, v); int temp2 = KnapsackCore(n - 1, v - volume[n]) + value[n]; return temp1 >= temp2 ? temp1 : temp2; } 第二种就是使用中间矩阵 $P$ 自底向上求取最优解。 具体怎样更新矩阵，下面以体积分别为 (1，2，3，4，5)，价值分别为 (5，4，3，2，1) 的五个物品为例，假设背包的容量为 10。根据状态转移方程有下表：

从左到右，从上到下更新每一行即可，其中的蓝 {MOD}箭头表示更新数值的计算对象，比如，$P[1][3] = P[1-1][3-2] + 4 = P[0][1] + 4 = 9$ 。 注意边界条件，超出边界的数值直接取0。比如求$P[1][1]$ 时，$P[1][1] = P[1-1][1-2] + 4 = P[0][-1] + 4 = 4$，很显然 $P[0][-1]$ 已经超出范围了，直接令 $P[0][-1] = 0$ ，所以 $P[1][1] = max(P[0][1], P[0][-1]+4) = 5$。迭代结束后，右下角就是最终的答案。 为什么使用 $v+1$ 列，而不是使用 $v$ 列呢？
首先 $v$ 是可以取到0的，我们允许输入为0，其次，便于代码直接使用数组的列标作为容量进行计算。 为什么使用 $n$ 行，而不使用 $n+1$ 行？
很多文章中解决的问题的矩阵大小是 $(n+1) * (v+1)$，其实使用 $n$ 还是 $n+1$ 都可以。使用 $n+1$ 行的矩阵就要求我们初始化的时候将第 0 行全部初始化为 0 ，然后从第 1 行开始更新，而使用 $n$ 行矩阵就需要注意边界条件，主要是第 0 行的更新需要做好判断。

2.1.3 代码

private static int Knapsack(int v, int[] value, int[] volume) throws Exception{ int n = volume.length; if