引言

动态规划问题在ACM中经常可以遇见，涉及到计数或者求解最优值时往往就有动态规划的身影。01背包问题本身比较简单，本节便由01背包问题入手，介绍一下动态规划的基本概念与方法。

基本模型

现要把N件物品装进一个大小为M的背包，第i件物品大小为w[i]，价值为v[i]。那么这个背包能装下物品的最大价值是多少？

模型分析

搜索显然是可以解决这个问题的，但效率无法令人满意。当然有记忆化搜索的方法来提高效率，这些内容将会在后面章节具体介绍。贪心的做法也非常直观，每次先放价值最大的，但这样做并不一定能得到最优解，这里也就不再赘述了。

现在的问题是要用n个物品填充大小为m的背包，使得价值最大。实际上需要考虑的就是对于每件物品用还是不用，这n件物品的顺序是无所谓的，所以我们不妨先从最后一件物品入手。

如果我们使用第n件物品，那么将获得v[n]的价值，背包的空间剩余m-w[n]。那么我们接下来要做的就是用前n-1件物品，填充大小为m-w[n]的背包，同样也是要获得尽可能多的价值。当然使用第n件物品有一个前提，就是能把它装下，即m>=w[n]。

如果我们不使用第n件物品，那么接下来需要用前n-1件物品，填充大小为m的背包，使得价值最大。

在上面的分析中，频繁地出现了一个同样的问题，就是用某些物品填充大小一定的背包，获得的最大价值是多少。只要每件物品的大小和价值给定，这个最大价值一定是客观存在的，只是暂时我们还不清楚而已。所以我们不妨用f(i,j)表示：使用前i个物品，填充大小为j的背包，所能获得的最大价值。

那么我们前面的分析就可以整理成如下的公式：

如果使用第n件物品，f(n,m)=v[n]+f(n-1,m-w[n])；

如果不使用第n见物品，f(n,m)=f(n-1,m)。

既然是想要获得最大价值，自然是要在上面两种情况中选择一个最好的结果。如果v[n]+f(n-1,m-w[n])比f(n-1,m)大，那就使用第n件物品；比后者小就不用；两者相等的话用不用皆可。

$f(n,m) = \max \left\{ {\matrix{ {v[n] + f(n - 1,m - w[n])} & {if(m \ge w[n])} \cr {f(n - 1,m)} & {} \cr } } \right.$，

以上是对初始情况，用前n个物品填大小为m的背包的情况进行分析。同理，对于任意的i和j，想用前i件物品填大小为j的背包，也可以进行完全相同的分析，即考虑用不用第i件物品。所以对于f(i,j)也可以列出类似的公式：

$f(i,j) = \max \left\{ {\matrix{ {v[i] + f(i - 1,j - w[i])} & {if(j \ge w[i])} \cr {f(i - 1,j)} & {} \cr } } \right.$。

这样，如果我们已经知道了f(i-1,...)的值，那么利用上面的公式就可以很轻松地把f(i,...)的值全部求出来。那么又如何求f(i-1,...)的值呢？答案其实是显而易见的，那就是用f(i-2,...)。你要是再问怎么求f(i-2,...)，那我也只能告诉你用f(i-3,...)的值来求……

现在问题来了，这样推脱下去，什么时候是个头呀？

我们不妨考虑一下f(0,...)的含义。用前0件物品去填某个大小的背包，能获得的最大价值。“前0件物品”自然就是说已经没有物品可用了。既然没有物品可用，那么也就无需考虑用与不用了。物品都没有了，就算背包再大，获得的价值也只能是0，所以f(0,...)一定都等于0。

现在我们已经知道了f(0,...)的值，那么也就可以算出f(1,...)、f(2,...)、f(3,...)……二世三世至于万世，传之无穷。f(n,m)的值自然也就可以求出来了。

概念简介

在上面的分析中，我们用f(i,j)表示：使用前i个物品，填充大小为j的背包，所能获得的最大价值。这里的f(i,j)就叫做状态（也可称之为阶段），用来表示我们要求解的同一类问题。

$f(i,j) = \max \left\{ {\matrix{ {v[i] + f(i - 1,j - w[i])} & {if(j \ge w[i])} \cr {f(i - 1,j)} & {} \cr } } \right.$

这个求解f(i,j)的公式叫做状态转移方程。我们利用状态转移方程，就可以用较小规模的状态，求解出较大规模的状态。本例中就是用f(i-1,...)来计算f(i,...)。

在利用方程进行状态转移的过程中，往往需要对多种情况取一个最优值。本例中就体现在对于第i件物品，用还是不用。这种选择被称作决策。

当状态的规模小到一定程度之后，往往就可以直接算出结果，而不再需要状态转移方程了。比如本例中的f(0,...)=0，就是边界条件。

有了边界条件，再利用状态转移方程，就可以求出所有的状态了，原问题也就迎刃而解。这一算法的正确性，用数学归纳法便可证明。

具体实现

算法已经有了，接下来的问题便是具体如何求解每一个状态。

我们用f(i,j)来表示状态，很自然的可以用一个二维数组存储每一个状态的值。求解的过程就像是在填表格，当把这个n*m的表格填满，我们也就得到了最终的答案。

当边界条件和状态转移方程确定后，我们所要考虑的就是要按照什么样的顺序来求解所有状态。因为一个较大规模的状态依赖于若干个较小规模的状态，所以我们要确保较大规模的状态要放在较小规模的状态之后求解。

在本例中f(i,...)依赖于f(i-1,...)的结果，所以我们可以按照第一维从小到大的顺序来求解所有状态。首先把边界的状态确定，然后一个二重循环把表格填满即可。

核心代码

for(j=0;j<=m;j++) f[0][j]=0;
for(i=1;i<=n;i++)
       for(j=0;j<=m;j++)
       {
              f[i][j]=f[i-1][j];
              if(j>=w[i])
              {
                     tmp=v[i]+f[i-1][j-w[i]];
                     if(tmp>f[i][j]) f[i][j]=tmp;
              }
       }//f[n][m] is the answer

written by PCZ