动态规划背包相关问题1-整数背包问题解析

从这篇短文开始将准备陆续介绍一下动态规划中的背包问题，这次主要介绍01背包问题的求解方法及分析。所谓01背包问题，就是N个物体中每一个物体要么不放入背包（0状态），要么一个物体要完整的放入背包（1状态）。具体问题描述如下。

有 N件物品和一个容量是 V的背包。每件物品只能使用一次。第 i件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。输入格式第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。接下来有 N行，每行两个整数 vi,wi，用空格隔开，分别表示第 i件物品的体积和价值。输出格式输出一个整数，表示最大价值。数据范围0<N,V≤1000，0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8

分析：我们可以看出，每个物体要么放入（状态为1），要么不放（状态为0）有两种状态，N种物体会有2的N次幂种状态（当然有些状态会不满足条件，如总容量超标），用这种组合枚举的方式计算量会比较大（算法复杂度）。下面就用深度优先搜索的方式去向大家介绍此种方法的实现。首先我们贴上代码如下：

//深度优先搜索算法
int dfs_solver(int idx, int spV){
    int result;
    if(idx > N){
        return 0;
    }else if(spV < v[idx]){
        result = dfs_solver(idx+1, spV);
    }else if(spV >= v[idx]){
        result = std::max(dfs_solver(idx+1, spV-v[idx])+w[idx], dfs_solver(idx+1, spV));
    }
    return result;
}

上述代码的浅析过程如下：第一个参数idx表示已经从第一个物体搜索到第idx的物体的放置状态，spV表示当前idx个物品放置状态下还有spV剩余的容量。初始调用时的参数状态为dfs_solver(1, V)，这里为了方便，物体索引从1开始，根据c/c++以及python的语言规范，下表0的相关数据为冗余空间。在这里我们以上述的输入样例来说明深度优先遍历的搜索过程。如下图所示：

上述的基于深度优先遍历的递归实现方式是物品组合方式的一种实现，效率不是很高，因为有上述的递归搜索树的实现，在程序调用上，递归函数实现过程会涉及函数及其参数的多次入栈和退栈（寄存器的一些操作，可以参考引文），这也是影响效率的主要原因（基于递归也可以有一定的优化，如有的调用参数状态会重复，这样的状态调用可以将结果暂存起来）。

而动态规划是一种基于递推的实现，计算的中间过程不断朝着目标状态演进。动态规划的实现主要是要合理的定义状态矩阵和写出状态转移方程，这里我们用二维数组dp[i][j]来描述01背包的状态，其中第一个维度的i表示已经处理到第i个物体，第二个维度的j表示容量为j时背包所装下的所有可能物体的价值总和的最大值，因此问题下的最优结果为dp[N][V](为了表示方便，下标从1开始，在c/c++和python中会引起一定的空间浪费)。基于此状态矩阵表示，这里01背包的状态方程可以写成如下的等式：

dp[i][j] = max(dp[i-1][j-v[i]]+w[i], dp[i-1][j])。

也就是遍历到第i个物体总容量为j的背包所能容下物体的总价值的最大值为下面两种状态下的较大的值：

第一种：dp[i-1][j-v[i]]+w[i]，为前i-1种物体在容量为j-v[i]的状态的最大值下再放入物体i后形成的值；第二种：dp[i-1][j]为前i-1种物体在容量为j的状态的最大值下不放入第i个物体的最大值。当然也要满足容量的约束条件，而且在i为1时，j只要大于v[1], 所有的后面的d[1][>v[1]]的值均为w[1]，dp[1][<v[1]]的值均为0，这个可以认为是作为初始化条件。因此，整个动态规划的逻辑代码可以表示为如下：

int dp_solver()
{
    for(int i = 1; i < N+1; i++)
    {
        for(int j = 1; j < V+1; j++){
            if(j >= v[i] && i==1)//第1个物体，请容量大于该物体时的价值
            {
                dp[i][j] = w[i];
            }else if(j < v[i] && i==1){
                dp[i][j] = 0;//第1个物体，容量小于该物体，则放不下价值为0
            }
            else if(i > 1 && j >= v[i]){
                dp[i][j] = std::max(dp[i-1][j-v[i]]+w[i], dp[i-1][j]);
            }else if(i > 1 && j < v[i])
            {
                dp[i][j] = dp[i-1][j];//第i个物体，但容量要小于该物体，该物体在此状态下放不下背包。
            }
        }
    }
    cout << dp[N][V];    
}

后续将继续向大家介绍关于背包相关问题的解决方案。

References

• C语言函数调用栈 – 知乎 (zhihu.com)