一、问题理解：什么是 0-1 背包？

我们先把问题用通俗的语言讲清楚：

小明有一个容量为 V 的背包，面前有 n 个物品，每个物品有两个属性 —— 体积 volume[i] 和价值 value[i]。每个物品只能选或不选（这就是 “0-1” 的含义），请问如何选择物品放入背包，才能在不超过背包容量的前提下，让背包内物品的总价值最大？

二、第一版代码：暴力递归（问题重重）

先来看最直观的递归实现 —— 直接翻译问题的 “选 / 不选” 逻辑，这也是很多新手的第一思路：

int bag(int volume[],int value[],int current_volume,int n){
  if(n == 0||current_volume == 0){
    return 0;
  }
  if(volume[n-1]>current_volume){
    return bag(volume,value,current_volume,n-1);
  }
  if(volume[n-1]<=current_volume){
    return bag(volume,value,current_volume-volume[n-1],n-1) + value[n-1]> bag(volume,value,current_volume,n-1) ? bag(volume,value,current_volume-volume[n-1],n-1)+value[n-1]  :  bag(volume,value,current_volume,n-1);
  }

}

第一版代码的核心问题

这个代码能得到正确结果，但存在致命缺陷，完全不适合实际使用：

1. 重复计算子问题（效率灾难）递归过程中，大量相同的 “剩余容量 + 剩余物品数” 组合会被反复计算。比如计算bag(..., 5, 3)时，可能会多次调用bag(..., 3, 2)，时间复杂度是 O(2^n)—— 当物品数n=20时，计算量就超过百万；n=30时，计算量突破十亿，直接超时。
2. 语法隐患代码最后缺少默认返回值，虽然逻辑上不会走到这一步，但编译器会报警告，且不符合代码规范。
3. 递归栈开销递归深度等于物品数，若n过大（比如 1000），会触发栈溢出。

三、第一轮优化：记忆化搜索（递归 + 备忘录）

针对 “重复计算子问题” 的核心问题，最直接的优化是记忆化搜索—— 用一个 “备忘录” 记录已经计算过的子问题结果，避免重复计算。

#include <iostream>
#include <cstring> // 用于memset初始化
using namespace std;

// 备忘录：memo[n][v] 表示“前n个物品、剩余容量v”时的最大价值
int** memo;

// 方向：简化max函数（避免重复写三元运算符）
int max(int a, int b) {
    return a > b ? a : b;
}

// 记忆化搜索版背包函数
int bag_memo(int volume[], int value[], int current_volume, int n) {
    // 基准条件
    if (n == 0 || current_volume == 0) {
        return 0;
    }
    
    // 核心优化：先查备忘录，有结果直接返回
    if (memo[n][current_volume] != -1) {
        return memo[n][current_volume];
    }
    
    int res;
    // 物品体积超容量，只能不选
    if (volume[n-1] > current_volume) {
        res = bag_memo(volume, value, current_volume, n-1);
    } else {
        // 选：剩余容量-当前物品体积，价值+当前物品价值
        int select = bag_memo(volume, value, current_volume - volume[n-1], n-1) + value[n-1];
        // 不选：容量和物品数都减1
        int not_select = bag_memo(volume, value, current_volume, n-1);
        res = max(select, not_select);
    }
    
    // 存入备忘录，供后续复用
    memo[n][current_volume] = res;
    return res;
}

int main() {
    int volume[] = {2, 3, 4, 5};
    int value[] = {3, 4, 5, 6};
    int total_volume = 8;
    int n = sizeof(volume)/sizeof(volume[0]);
    
    // 初始化备忘录：(n+1)行（物品数）、(total_volume+1)列（容量）
    memo = new int*[n+1];
    for (int i = 0; i <= n; i++) {
        memo[i] = new int[total_volume + 1];
        // 初始值-1，表示该子问题未计算
        memset(memo[i], -1, (total_volume + 1) * sizeof(int));
    }
    
    int max_value = bag_memo(volume, value, total_volume, n);
    cout << "最大价值：" << max_value << endl; // 输出10
    
    // 释放内存（避免内存泄漏）
    for (int i = 0; i <= n; i++) {
        delete[] memo[i];
    }
    delete[] memo;
    
    return 0;
}

关键优化点详解

1. 备忘录的核心作用memo[n][v] 是 “状态缓存”，存储 “前 n 个物品、剩余容量 v” 时的最大价值。第一次计算后存入，后续遇到相同状态直接读取，彻底解决重复计算问题。
2. 时间复杂度骤降每个子问题（n和v的组合）只计算一次，时间复杂度从 O(2^n) 降到 O(n∗V)（n为物品数，V为背包容量）。
3. 代码可读性提升抽离max函数，避免冗长的三元运算符，逻辑更清晰；补充内存释放逻辑，符合 C++ 规范。

四、第二轮优化：迭代版二维 DP（消除递归栈）

记忆化搜索解决了效率问题，但递归仍有栈开销。我们可以用迭代填充 DP 表的方式，彻底摆脱递归，这也是动态规划的标准实现。

#include <iostream>
using namespace std;

int max(int a, int b) {
    return a > b ? a : b;
}

// 迭代版二维DP求解0-1背包
int bag_dp_2d(int volume[], int value[], int total_volume, int n) {
    // 状态定义：dp[i][j] 表示“前i个物品、背包容量j”时的最大价值
    int dp[n+1][total_volume+1];
    
    // 初始化：0个物品 或 0容量时，价值为0
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
    for (int j = 0; j <= total_volume; j++) {
        dp[0][j] = 0;
    }
    
    // 填充DP表：遍历每个物品、每个容量
    for (int i = 1; i <= n; i++) { // 第i个物品（对应数组下标i-1）
        for (int j = 1; j <= total_volume; j++) { // 背包容量j
            if (volume[i-1] > j) {
                // 物品体积超容量，只能不选，继承前i-1个物品的结果
                dp[i][j] = dp[i-1][j];
            } else {
                // 选或不选，取最大值
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - volume[i-1]] + value[i-1]);
            }
        }
    }
    
    return dp[n][total_volume];
}

int main() {
    int volume[] = {2, 3, 4, 5};
    int value[] = {3, 4, 5, 6};
    int total_volume = 8;
    int n = sizeof(volume)/sizeof(volume[0]);
    
    int max_value = bag_dp_2d(volume, value, total_volume, n);
    cout << "最大价值：" << max_value << endl; // 输出10
    return 0;
}

关键优化点详解

1. 状态转移方程（核心）动态规划的灵魂是状态转移，这里的核心逻辑可以总结为：dp[i][j]={dp[i−1][j]max(dp[i−1][j],dp[i−1][j−volume[i−1]]+value[i−1])​若 volume[i−1]>j(物品体积超容量，不选)否则（选/不选取最大值）​
2. 消除递归栈迭代方式没有递归调用，避免了栈溢出风险，且执行效率更高（少了函数调用的开销）。
3. 状态定义更直观dp[i][j] 直接对应 “前 i 个物品、容量 j” 的状态，新手更容易理解动态规划的 “状态” 和 “决策” 思想。

五、终极优化：一维 DP（空间压缩到极致）

观察二维 DP 的状态转移方程会发现：dp[i][j] 只依赖 dp[i-1][j]（上一行同列）和 dp[i-1][j-volume[i-1]]（上一行左侧列）。因此，我们可以将二维数组压缩为一维数组，空间复杂度从 O(n∗V) 降到 O(V)。

#include <iostream>
using namespace std;
int max(int a,int b){
  return a>b?a:b;
}
int bag(int volume[],int value[],int total_volume,int n){
  int max_value[total_volume+1];//不同容量的最大价值
  for(int i = 0;i <= total_volume;i++){
    max_value[i]=0;
  }
  for(int i = 0;i < n;i++){
    for(int j = total_volume;j >= volume[i];j--){
      max_value[j]=max(max_value[j],max_value[j-volume[i]]+value[i]);
    }
  }
  return max_value[total_volume];
}

int main()
{
  // 请在此输入您的代码
  int N,V;
  cin>>N>>V;
  int volume[N],value[N];
  for(int i = 0;i < N;i++){
    cin>>volume[i]>>value[i];
  }
  cout<<bag(volume,value,V,N);
  return 0;
}

关键优化点详解

1. 空间压缩原理一维数组dp[j]复用了二维数组的 “上一行” 数据，每次处理新物品时，从后往前更新，保证不会覆盖还未使用的 “上一行” 数据。
2. 逆序遍历的核心原因0-1 背包中每个物品只能选一次，逆序遍历容量能确保计算dp[j]时，dp[j-volume[i]]还是 “未选当前物品” 的状态（上一轮结果）；如果正序遍历，会导致同一物品被多次选取（变成 “完全背包” 问题）。
3. 代码极简且高效一维 DP 是 0-1 背包的最优实现，代码行数最少、空间占用最小，也是面试中最常考察的版本。

六、总结：0-1 背包优化的核心思想

从暴力递归到一维 DP，我们的优化过程本质上是对动态规划核心思想的逐步落地：

1. 重叠子问题：用备忘录 / DP 表缓存重复计算的子问题，将指数级时间复杂度降到多项式级别；
2. 最优子结构：“选 / 不选” 的决策依赖子问题的最优解，符合动态规划的 “最优子结构” 特性；
3. 空间压缩：通过观察状态转移的依赖关系，移除冗余的维度，实现空间最优。

对于编程新手来说，建议按 “暴力递归→记忆化搜索→二维 DP→一维 DP” 的顺序学习：先理解递归的 “选 / 不选” 逻辑，再掌握动态规划的状态定义和转移，最后吃透一维 DP 的空间压缩技巧 —— 这不仅能解决 0-1 背包问题，也能为后续学习完全背包、多重背包等扩展问题打下坚实基础。