动态规划背包问题浅析

在前一篇文章的结尾中提到了动态规划算法，这里再简要的说下吧。网上关于动态规划的讨论也比较多，看来看去，大部分人还是充当了搬运工。还是建议《算法导论》吧。下面简要总结一下。

动态规划的思想是对于每个子问题只求解一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算答案（这个描述感觉有点像搜索）。动态规划算法的两个要素：最优子结构和重叠子问题。如何判断呢？简单来说，如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。注意这时候一般来说也可以用贪心算法来解，但是贪心算法与动态规划算法有一个本质的区别：贪心算法的思想是局部最优解，而动态规划算法的思想是全局最优解。那么重叠子问题是什么意思呢？用来解决原问题的递归算法可反复地解同样的子问题。典型地，不同的子问题数是输入规模的一个多项式。当一个递归算法不断地调用同一问题时，我们说该最优问题包含重叠子问题。下面主要来讨论一下典型的动态规划问题——背包问题以及一点扩展。

首先来看01背包问题。有n个重量和价值分别为w[i]，v[i]的物品。从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。如果看了上一篇文章的话，第一反应应该是状态搜索。其实很多问题都可以有搜索来解决，但是状态搜索的复杂度极高，主要是因为对很多状态重复计算。这时候在想一想上面说的，很容易可以想到，将所有状态都求解出来放到一张表里来避免重复计算，这就是动态规划了。

动态规划的求解思路一般是找到状态转移方程，定义初始状态，然后就可以递归的计算其它状态了。那么01背包的状态转移方程应该怎样来求解呢？定义状态函数dp[i]+1[j]表示从前i种物品中挑选总重量不超过j时总价值的最大值。初始化dp[0][j]=0。对于第i件物品，有两个选择，选或者不选，这时候状态转移方程为dp[i+1][j]=max(dp[i][j], dp[i][j-w[i]]+v[i])，前面的对应不选。除此之外还要注意一种情况，就是当前物品的重量比j要大，这时就肯定不能选了。这些推导出来代码就很好写了。dp[n][W]即为所求。

for(int i=0; i<n; i++)
{
    for(int j=0; j<=W; j++)
    {
        if(j<W[i])
            dp[i+1][j] = dp[i][j];
        else
            dp[i+1][j] = max(dp[i][j], dp[i][j-W[i]]+v[i]);
    }
}

下面再来看一下完全背包问题。有n种重量和价值分别为w[i]，v[i]的物品。从这些物品中挑选总重量不超过W的物品，求出挑选物品价值总和的最大值。在这里，每种物品可以挑选任意多件。这时候同一各类的物品可以选择任意多件了。像01背包一样定义状态函数dp[i+1][j]表示从前i种物品中挑选总重量不超过j时的总价值的最大值。初始化dp[0][j]=0。对于每种物品可以先任意多次，那么状态转移方程类似可以写出来：dp[i+1][j] =max{dp[i][j-kw[i]]+kv[i] | 0<=k}。则dp表可以如下求出来。

for(int i=0; i<n; i++)
{
    for(int j=0; j<=W; j++)
    {
        for(int k=0; k*w[i]<=j; k++)
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-k*w[i]]+k*v[i]);
    }
}

仔细分析一下，我们就会发现上面还是存在重复计算，在dp[i+1][j]的计算中选择k（k>=1）个的情况，与在dp[i+1][j-w[i]]的计算中选择k-1个的情况是相同的，所以dp[i+1][j]的递推中k>=1部分的计算已经在dp[i+1][j-w[i]]的计算中完成了。那么可以推出：

max{dp[i][j-k*w[i]]+k*v[i] | k>=0} = max{dp[i][j], max{dp[i][j-k*w[i]]+k*v[i]|k>=1}}=max{dp[i][j], max{dp[i][j-w[i]-k*w[i]]+k*v[i]|k>=0}+v[i]}=max{dp[i][j], dp[i+1][j-w[i]]+v[i]}。

这样一来就不需要关于k的循环了。

for(int i=0; i<n; i++)
{
    for(int j=0; j<=W; j++)
    {
        if(j<w[i])
            dp[i+1][j] = dp[i][j];
        else
            dp[i+1][j] = max(dp[i][j], dp[i+1][j-w[i]]+v[i]);
    }
}

扩展，上面的问题中的空间复杂度都是O(nW),其实可以通过不断得利利用一个数组来实现。

int dp[W+1];

//01背包
for(int i=0; i<n; i++)
    for(int j=W; j>=w[i]; j--)
        dp[j]=max(dp[j], dp[j-w[i]]+v[i]);

//完全背包
for(int i=0; i<n; i++)
    for(int j=w[i]; j<=W; j++)
        dp[j] = max(dp[j], dp[j-w[i]]+v[i]);

另外topcoder上面的动态规划教程也很不错，推荐。Dynamic Programing