动态规划的核心思想是将复杂问题拆解为若干个相互关联的子问题，通过存储子问题的解来避免重复计算，最终得到原问题的最优解。背包问题是动态规划领域最经典的应用场景之一，其中0-1背包问题是最基础的形式，适合用来理解动态规划的实现逻辑和状态转移方程的推导过程。
0-1背包问题定义
0-1背包问题的具体描述为：给定n件物品和一个容量为W的背包，第i件物品的重量为weight[i]，价值为value[i]，每件物品只能选择放入背包一次或者不放入，求背包能装下的物品的最大总价值。
状态定义
动态规划的第一步是定义状态，对于0-1背包问题，我们定义dp[i][j]表示前i件物品放入容量为j的背包中能获得的最大价值。这里i的范围是0到n，j的范围是0到W。
DP状态转移方程推导
对于第i件物品（i从1开始计数），我们有两种选择：
- 不放入背包：此时最大价值等于前i-1件物品放入容量为j的背包的最大价值，即
dp[i][j] = dp[i-1][j] - 放入背包：此时需要保证背包容量j大于等于第i件物品的重量weight[i-1]（因为数组下标从0开始），放入后的价值为前i-1件物品放入容量为j-weight[i-1]的背包的最大价值加上第i件物品的价值value[i-1]，即
dp[i][j] = dp[i-1][j-weight[i-1]] + value[i-1]
我们取两种选择中的最大值作为dp[i][j]的结果，因此状态转移方程为：
当j < weight[i-1]时，dp[i][j] = dp[i-1][j]；
当j >= weight[i-1]时，dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]] + value[i-1])
基础版C++实现
根据上面的状态定义和转移方程，我们可以写出基础的二维DP实现代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int knapsack01(vector<int>& weight, vector<int>& value, int W) {
int n = weight.size();
// 定义dp数组，初始化为0
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
// 遍历物品
for (int i = 1; i <= n; i++) {
// 遍历背包容量
for (int j = 0; j <= W; j++) {
// 当前物品重量大于背包容量，无法放入
if (j < weight[i-1]) {
dp[i][j] = dp[i-1][j];
} else {
// 选择放入或不放入，取最大值
dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i-1]] + value[i-1]);
}
}
}
// 返回前n件物品放入容量为W的背包的最大价值
return dp[n][W];
}
int main() {
// 物品重量
vector<int> weight = {2, 3, 4, 5};
// 物品价值
vector<int> value = {3, 4, 5, 6};
// 背包容量
int W = 8;
int maxValue = knapsack01(weight, value, W);
cout << "背包能装下的最大价值为：" << maxValue << endl;
return 0;
}
空间优化版实现
上面的二维DP实现空间复杂度为O(n*W)，我们可以观察到dp[i][j]只和dp[i-1][*]有关，因此可以优化为一维数组，将空间复杂度降低到O(W)。需要注意的是，遍历背包容量时必须要从大到小遍历，避免同一件物品被重复放入。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int knapsack01Opt(vector<int>& weight, vector<int>& value, int W) {
int n = weight.size();
// 定义一维dp数组，初始化为0
vector<int> dp(W + 1, 0);
// 遍历物品
for (int i = 0; i < n; i++) {
// 逆序遍历背包容量，避免重复放入同一物品
for (int j = W; j >= weight[i]; j--) {
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
return dp[W];
}
int main() {
vector<int> weight = {2, 3, 4, 5};
vector<int> value = {3, 4, 5, 6};
int W = 8;
int maxValue = knapsack01Opt(weight, value, W);
cout << "优化后背包能装下的最大价值为：" << maxValue << endl;
return 0;
}
动态规划实现通用思路
通过背包问题的实现，我们可以总结出C++实现动态规划算法的通用步骤：
- 明确问题的状态定义，确定dp数组的含义和维度
- 推导状态转移方程，明确当前状态和之前子问题状态的关系
- 确定dp数组的初始化条件，避免边界错误
- 确定遍历顺序，保证计算当前状态时所需的子问题状态已经计算完成
- 根据状态转移方程编写代码，必要时进行空间优化
掌握这个思路后，我们可以应对更多类型的动态规划问题，比如最长公共子序列、最长递增子序列等问题，只需要根据具体问题调整状态定义和转移方程即可。