0-1背包问题通过动态规划求解，状态定义为dpi表示前i个物品在容量w下的最大价值，转移方程为dpi = max(dpi-1, dpi-1] + value[i-1])；C++实现采用二维数组填充DP表，可优化为一维数组从后往前更新，空间复杂度由O(nW)降为O(W)，适用于处理重叠子问题与最优子结构的最优化场景。
动态规划（Dynamic Programming，简称DP）是解决最优化问题的重要方法，尤其在处理具有重叠子问题和最优子结构的问题时非常高效。C++作为高性能编程语言，非常适合实现动态规划算法。下面以经典的0-1背包问题为例，讲解如何用C++实现动态规划，并推导状态转移方程。
什么是0-1背包问题？
给定n个物品，每个物品有重量weight[i]和价值value[i]，以及一个容量为W的背包。每件物品只能选择放入或不放入（即不能分割），目标是在不超过背包容量的前提下，使总价值最大。
DP状态定义与状态转移方程
关键在于设计合适的状态表示和递推关系。
状态定义：
立即学习“C++免费学习笔记（深入）”；
- 设dp[i][w]表示前i个物品，在背包容量为w时能获得的最大价值。
状态转移逻辑：
- 对于第i个物品（索引从1开始），有两种选择：
- 不放入：则最大价值等于dp[i-1][w]
- 放入（前提是w >= weight[i-1]）：则价值为dp[i-1][w - weight[i-1]] + value[i-1]
- 取两者最大值即可。
状态转移方程：
dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i-1]] + value[i-1])
C++代码实现
以下是完整的C++实现，使用二维数组存储DP表：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
<p>int knapsack(int W, vector<int>& weight, vector<int>& value) {
int n = weight.size();
// 创建DP表，初始化为0
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));</p><pre class="brush:php;toolbar:false;">// 填充DP表
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
// 不选第i个物品
dp[i][w] = dp[i-1][w];
// 如果能装下，尝试选择
if (w >= weight[i-1]) {
dp[i][w] = max(dp[i][w], dp[i-1][w - weight[i-1]] + value[i-1]);
}
}
}
return dp[n][W]; // 返回最大价值}
int main() {
vector
cout << "Maximum value: " << knapsack(W, weight, value) << endl; return 0;
}
空间优化：使用一维数组
观察发现，每次更新只依赖上一行的数据。因此可以用一维数组优化空间复杂度到O(W)。
关键点：内层循环要从后往前遍历，避免覆盖还未使用的状态。
int knapsack_optimized(int W, vector<int>& weight, vector<int>& value) {
int n = weight.size();
vector<int> dp(W + 1, 0);
<pre class="brush:php;toolbar:false;">for (int i = 0; i < n; i++) {
for (int w = W; w >= weight[i]; w--) {
dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
}
}
return dp[W];}
这种方法将空间从O(nW)降为O(W)，是实际应用中更常见的写法。
基本上就这些。掌握状态定义、转移方程推导和代码实现三步，就能应对大多数背包类DP问题。
