1. 问题定义
   
   

01背包问题是一个经典的组合优化问题，通常描述如下：

• 有个容量为C的背包

• 有n件物品，第i件物品的重量为Wi,价值为Vi

• 每种物品只有一件，可以选择放入背包（1）或不放入背包（0），因此称为“01”背包。

• 目标：在不超过背包容量的前提下，使装入背包的物品总价值最大。

  
  
  

2.动态规划解法

这是最常用的解法，核心是状态定义与状态转移方程。

（1）状态定义

设 $dp[i][j]$dp[i][j]表示：考虑前 $i$ 件物品，在背包容量为 $j$ 时能获得的最大价值。

• $i$ 的范围：$0\le i\le n$

• $j$ 的范围：$0\le j\le C$

（2）状态转移

对于第 i 件物品（体积 v[i]，价值 w[i]）：

1. 不选：dp[i][j] = dp[i-1][j]

2. 选（前提是 j >= v[i]）：dp[i][j] = dp[i-1][j - v[i]] + w[i]

取两者最大值：

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

（3）初始化

• dp[0][j] = 0（没有物品可选时，价值为 0）

• dp[i][0] = 0（背包容量为 0 时，无法装任何物品）

（4）参考代码

#include <iostream>  #include <algorithm>  using namespace std;    int main() {      int N, V;      cin >> N >> V;            int v[1005], w[1005];      for (int i = 1; i <= N; i++) {          cin >> v[i] >> w[i];      }        // dp[i][j] 表示前 i 件物品，容量 j 的最大价值      int dp[1005][1005] = {0};        for (int i = 1; i <= N; i++) {          for (int j = 0; j <= V; j++) { // 从 0 开始更规范              if (j < v[i]) {                  // 容量不够，只能不选                  dp[i][j] = dp[i - 1][j];              } else {                  // 容量足够，取“不选”和“选”的最大值                  dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);              }          }      }        cout << dp[N][V] << endl;      return 0;  }

• 当 j < v[i]：背包容量不够，不能选第 i 件物品，所以 dp[i][j] 直接等于 dp[i-1][j]。

• 当 j >= v[i]：可以选第 i 件物品，所以要取 “选” 和 “不选” 的最大值。

（5）例子详解

如果输入

4 5  1 2  2 4  3 4  4 5

背包容量： V = 5

开始逐步计算dp表

初始状态（i=0）：

容量 j: 0 1 2 3 4 5  dp[0]:  0 0 0 0 0 0

i=1（考虑第1件物品：体积1，价值2）

j=1: max(dp[0][1]=0, dp[0][0]+2=2) = 2  j=2: max(dp[0][2]=0, dp[0][1]+2=2) = 2  j=3: max(dp[0][3]=0, dp[0][2]+2=2) = 2  j=4: max(dp[0][4]=0, dp[0][3]+2=2) = 2  j=5: max(dp[0][5]=0, dp[0][4]+2=2) = 2    dp[1]: 0 2 2 2 2 2

i=2（考虑第2件物品：体积2，价值4）

j=1: dp[1][1]=2 (容量不够选物品2)  j=2: max(dp[1][2]=2, dp[1][0]+4=4) = 4  j=3: max(dp[1][3]=2, dp[1][1]+4=6) = 6  j=4: max(dp[1][4]=2, dp[1][2]+4=6) = 6  j=5: max(dp[1][5]=2, dp[1][3]+4=6) = 6    dp[2]: 0 2 4 6 6 6

i=3（考虑第3件物品：体积3，价值4）

j=1: dp[2][1]=2 (容量不够)  j=2: dp[2][2]=4 (容量不够)  j=3: max(dp[2][3]=6, dp[2][0]+4=4) = 6  j=4: max(dp[2][4]=6, dp[2][1]+4=6) = 6  j=5: max(dp[2][5]=6, dp[2][2]+4=8) = 8    dp[3]: 0 2 4 6 6 8

i=4（考虑第4件物品：体积4，价值5）

j=1: dp[3][1]=2 (容量不够)  j=2: dp[3][2]=4 (容量不够)  j=3: dp[3][3]=6 (容量不够)  j=4: max(dp[3][4]=6, dp[3][0]+5=5) = 6  j=5: max(dp[3][5]=8, dp[3][1]+5=7) = 8    dp[4]: 0 2 4 6 6 8

最终结果：

最大价值： dp[4][5] = 8

最优方案： 选择物品2（体积2，价值4）和物品3（体积3，价值4），总价值8，刚好用完容量5。

完整的dp表

关键点：

1. dp[i][j] = dp[i-1][j]：不选当前物品，继承前i-1件物品的最优解

2. dp[i-1][j-v[i]] + w[i]：选当前物品，用剩余容量 j-v[i] 在前i-1件物品中找最优解，加上当前物品价值

3. max(...)：在"选"和"不选"中选择价值更大的方案

3.一维数组优化

观察状态转移方程

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

发现 dp[i] 只依赖于 dp[i-1]，所以可以只用一维数组，倒序遍历容量，避免覆盖上一层的状态

一维 dp 定义：

dp[j] 表示容量为 j 的背包能装的最大价值。

状态转移：

dp[j]=max(dp[j], dp[j−v[i]]+w[i])

注意：j 从 V 到 v[i] 倒序遍历。

参考代码

#include <iostream>  #include <vector>  #include <algorithm>  using namespace std;    int main() {      int N, V;      cin >> N >> V;      vector<int> v(N + 1), w(N + 1);      for (int i = 1; i <= N; i++) {          cin >> v[i] >> w[i];      }        vector<int> dp(V + 1, 0);        for (int i = 1; i <= N; i++) {          // 必须倒序遍历，防止重复选择          for (int j = V; j >= v[i]; j--) {              dp[j] = max(dp[j], dp[j - v[i]] + w[i]);          }      }        cout << dp[V] << endl;      return 0;  }