0-1背包问题通过动态规划求解，使用二维数组dpi表示前i个物品在容量w下的最大价值，状态转移方程为dpi = max(dpi-1, dpi-1] + value[i])；可通过滚动数组优化为空间复杂度更低的一维形式，时间复杂度O(nW)，适用于中小规模问题。
0-1背包问题是经典的动态规划问题。给定n个物品，每个物品有重量和价值，一个背包有最大承重限制，要求在不超过背包容量的前提下，选择物品使得总价值最大，每种物品只能选一次。
动态规划思路
使用二维数组 dp[i][w] 表示前i个物品在背包容量为w时能获得的最大价值。
状态转移方程：
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
立即学习“C++免费学习笔记（深入）”；
其中：
- 如果不选第i个物品：dp[i][w] = dp[i-1][w]
- 如果选第i个物品（前提是weight[i] ≤ w）：dp[i][w] = dp[i-1][w-weight[i]] + value[i]
C++实现代码
#include <iostream>
#include <vector>
using namespace std;
<p>int knapsack(int W, vector<int>& weight, vector<int>& value) {
int n = weight.size();
// 创建二维DP表
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];
// 如果能装下第i个物品，尝试选择它
if (weight[i-1] <= w) {
dp[i][w] = max(dp[i][w], dp[i-1][w - weight[i-1]] + value[i-1]);
}
}
}
return dp[n][W];}
int main() { vector<int> value = {60, 100, 120}; vector<int> weight = {10, 20, 30}; int W = 50; cout << "最大价值: " << knapsack(W, weight, value) << endl; return 0; }
优化空间复杂度（滚动数组）
可以将二维DP优化为一维数组，减少空间使用。
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)，适合中小规模问题。
