动态规划之背包问题详解：从基础到应用

动态规划之背包问题详解：从基础到应用

动态规划中的背包问题是一个非常重要的主题，本文将系统地总结01背包问题的二维dp数组和一维dp数组的实现方法，并通过具体的例子和图示帮助理解。此外，还将介绍如何将01背包问题应用于实际的算法题目中，如分割等和子集和最后一块石头的重量问题。

01背包问题的二维dp数组实现

在01背包问题中，我们首先需要确定dp数组以及下标的含义。dp[i][j]表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

接下来是递推公式的推导：

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

在初始化dp数组时，需要特别注意边界条件：

// 初始化 dp
vector<vector<int>> dp(weight.size() + 1, vector<int>(bagWeight + 1, 0));
for (int j = bagWeight; j >= weight[0]; j--) {
    dp[0][j] = dp[0][j - weight[0]] + value[0];
}

遍历顺序上，01背包二维dp数组在遍历顺序上，外层遍历物品，内层遍历背包容量和外层遍历背包容量，内层遍历物品都是可以的。但是先遍历物品更好理解：

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 这个是为了展现dp数组里元素的变化
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

以背包最大重量为4，物品重量和价值如下为例：

对应的dp数组的数值如下图所示：

01背包问题的一维dp数组实现

在01背包问题的一维dp数组实现中，dp数组的定义为：dp[j]表示容量为j的背包，所背的物品价值可以最大为dp[j]。

递推公式为：

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

初始化时，如果物品价值都是大于0的，所以dp数组初始化的时候，都初始为0就可以了。

遍历顺序为：

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

应用实例

接下来，我们来看两个实际应用的例子：

分割等和子集

在"分割等和子集"问题中，我们需要确定以下四点：

• 背包的体积为sum / 2
• 背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值
• 背包如何正好装满，说明找到了总和为 sum / 2 的子集
• 背包中每一个元素是不可重复放入

接下来就是一个完整的01背包问题，大家应该可以轻松做出。

最后一块石头的重量

在"最后一块石头的重量"问题中，其实和"分割等和子集"是非常像的。本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。"分割等和子集"相当于是求背包是否正好装满，而本题是求背包最多能装多少。这两道题目是对dp[target]的处理方式不同。这也考验的对dp[i]定义的理解。

总结

总体来说，本文内容信息量较大，特别适合有一定编程基础并对动态规划感兴趣的读者。通过本文的学习，读者应该能够掌握01背包问题的二维dp数组和一维dp数组的实现方法，并能够将这些知识应用到实际的算法题目中。