给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi。问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？

面对每个物品，我们只有选择拿(1)取或者不拿(0)两种选择，不能选择装入某物品的一部分，也不能装入同一物品多次。 把物品随机排成一排，标记为1、 2、 3……，从1号物品开始依次判断是否装包，面对当前物品有两种情况：

因此，通过判断当前物品是否装包而计算当前问题的最优解时，是要用到上一个子问题的最优解的（通过判断上一个物品是否装包而计算得到），也就是说，如果当前物品不装进背包，那么上一个子问题的最优解就是当前状态的最优解，如果当前物品装包后的价值大于不装的价值，那么当前问题的最优解就是当前物品装进背包后产生的价值，这个值=上一个子问题中背包容量为【背包总容量减去当前物品重量】的情况下的最优解+当前物品价值。总之，当前问题的最优解求解过程依托于上一个子问题的各个状态下的最优解，所以在求当前问题的最优解之前要先求出之前的所有情况下的最优解。也就是要先求子问题的最优解。这里就需要用到动态规划的方法。

动态规划（Dynamic Programming,DP) 与分治法的区别在于划分的子问题是有重叠的，解过程中对于重叠的部分只要求解一次，记录下结果，减少了重复计算过程。 另外，DP在求解一个问题最优解时，不是固定的计算合并某些子问题的解，而是根据各子问题的解的情况选择其中最优的。 动态规划求解具有以下性质： 最优子结构性质：最优解包含了其子问题的最优解，不是合并所有子问题的解，而是找最优的一条解线路，选择部分子最优解来达到最终的最优解。 子问题重叠性质：先计算子问题的解，再由子问题的解去构造问题的解（由于子问题存在重叠，把子问题解记录下来为下一步使用，这样就可以从备忘录中读取）。其中备忘录先记录初始状态。

定义一个二维数组m[n][C]，每个元素代表一个状态，m[i][j]表示前 i 个物品放入容量为 j 的背包所能获得的最大价值，我们可以很容易分析得出m[i][j]的计算方法：

最后一行代码就是根据“为了容量为C的背包中物品总价值最大化，第i件物品应该放入背包中吗”转化来的。v(i)表示第i件物品的价值，w(i)表示第i件物品的重量。m[i-1][j]表示不将这件物品放进背包的背包的总价值，m[i-1][j-v(i)]+w(i)表示将第i件物品放进背包后背包的总价值，比较两者，取最大值作为最终的选择。 假设有6个物品： 价值数组v = {8, 10, 6, 3, 7, 2}， 重量数组w = {4, 6, 2, 2, 5, 1}， 求背包容量C = 12时对应的m[i][j]数组。