【算法打卡day12（2026-02-28 周六）01背包基础理论】

- 第 174 篇 -
Date: 2026 - 02- 28 | 周六
Author: 郑龙浩（仟墨）
算法：动态规划（DP）

01背包基础理论

文章目录

• 01背包基础理论
  • 1 三种背包基本介绍
  • 2 纯01背包问题

完全背包 和 多重背包 都是 以 【01背包】为基础得来的， 所以【01背包】是重中之重，一定要把01背包搞清楚，才能把完全背包理解透彻

1 三种背包基本介绍

1. 01 背包：有n种物品，每种物品只有1个
2. 完全背包：有n种物品，每种物品有无限个
3. 多重背包：有n种物品，每种物品的个数各不相同
   多重背包可以忽略，蓝桥杯和面试笔试几乎不考此类题目

力扣上没有纯的01背包和完全背包的题目，都是应用类的题目，都是引用01背包来解决某些问题

2 纯01背包问题

【问题描述】
有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的总重量不超过背包容量，且总价值最大。每种物品只能选择0个或1个。

【输入格式】

• 第一行：两个整数N和V，表示物品数量和背包容量
• 接下来N行：每行两个整数w[i]和v[i]，表示第i件物品的重量和价值

【输出格式】

• 一个整数，表示最大价值

DP解法1

dp[i][j]含义： 考虑前i个物品，在背包容量为j的情况下，能够获得的最大总价值

• i：表示我们考虑的是前i个物品（从1到N编号）
  • i = 0表示考虑0个物品（即没有物品）
  • i = 1表示只考虑第1个物品
  • i = 2表示考虑到第2个物品
  • …
  • i = N表示考虑所有N个物品
• j：表示当前背包的剩余容量
  • j = 0表示背包容量为0（不能装任何物品）
  • j = 1表示背包容量为1（只能放1个物品）
  • j = 2表示背包容量为2（可以放2个物品）
  • …
  • j = V表示背包容量为V（最大容量）

举个例子

假设有4个物品：

物品1：重量2，价值3 物品2：重量3，价值4 物品3：重量4，价值5 物品4：重量5，价值6 背包容量V = 8 

那么：

• dp[2][5]表示：只考虑前2个物品（物品1和物品2），在背包容量为5的情况下，能够获得的最大价值
  • 可能的组合：
    • 只放物品1：价值3
    • 只放物品2：价值4
    • 都放：重量2+3=5 ≤ 5，价值3+4=7
  • 所以 dp[2][5] = 7
• dp[3][6]表示：考虑前3个物品（物品1、2、3），在背包容量为6的情况下，能够获得的最大价值

【状态转移解释（两种情况）】

if(j >= w[i -1]){// 情况1：能放下第i个物品 dp[i][j]=max( dp[i -1][j],// 不放第i个物品 dp[i -1][j - w[i -1]]+ v[i -1]// 放第i个物品);}else{// 情况2：放不下第i个物品 dp[i][j]= dp[i -1][j];// 只能不放}

【我的困惑点：第i个物品或者物品i为什么是i-1而不是i？】
首先i是从1开始遍历的，这就导致了要取出第i个物品的 重量 或者 价值，就必须使用 w[i - 1] Or v[i - 1]
*DP状态中提到的“第 i 个物品”，对应到数组里，就是第 i-1号元素
w[0], v[0]→ 存储的是第一个物品的重量和价值。
w[1], v[1]→ 存储的是第二个物品的重量和价值。
也就是因为v数组和w数组是从下标0开始记录第1个物品的，所以第1个物品重量指的就是下标0重量，第6个物品指的就是下标5重量

情况1：当前背包容量 能放下【物品i】 (j >= w[i-1])

j >= w[i - 1]：当前背包容量j大于等于【物品i】的重量w[i-1]
此时就要判断是放【物品i】价值最大，还是不放【物品i】价值最大

• 情况1.1：不放【物品i】：dp[i-1][j]
  • 如果不放【物品i】，那么最优解就是前i-1个物品在容量j下的最优解
• 情况1.2：放【物品i】：dp[i-1][j - w[i-1]] + v[i-1]
  如果放【物品i】，假设先放入了【物品i】，就要用 当前容量 - 【物品i】所占容量得出的剩余容量（j - w[i - 1]），去判断在剩下这些容量能放的物品的最大价值是多少，也就是直接利用剩余空间（j - w[i - 1]）去找即可，dp[i - 1][j - w[i - 1]]
  • 如果放【物品i】，需要先给这个物品腾出空间 w[i-1]
  • 那么剩下的容量是 j - w[i-1]（当前容量 - 【物品i】所占空间）
  • 在前i-1个物品中，用容量 j - w[i-1]能获得的最大价值是 dp[i-1][j - w[i-1]]
  • 再加上【物品i】的价值 v[i-1]

情况2：当前背包容量 放不下【物品i】 (j < w[i-1])

当前背包容量j小于【物品i】的重量w[i-1]

• 只能选择不放【物品i】：dp[i][j] = dp[i-1][j]

【代码】

/* 【纯01背包问题-二维DP】 有N件物品和一个容量为V的背包。第i件物品的重量是`w[i]`，价值是`v[i]`。 求解将哪些物品装入背包可使这些物品的总重量不超过背包容量，且总价值最大。每种物品只能选择0个或1个。 【输入格式】 - 第一行：两个整数N和V，表示物品数量和背包容量 - 接下来N行：每行两个整数`w[i]`和`v[i]`，表示第i件物品的重量和价值 【输出格式】 - 一个整数，表示最大价值 Author：郑龙浩 Date：2026-02-28 用时：12min *//* #include "bits/stdc++.h" using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, V; cin >> N >> V; int w[N], v[N]; for (int i = 0; i < N; i++) cin >> w[i] >> v[i]; // dp[i][j] 表示考虑前i个物品，在背包容量为j时，能获得的最大价值 vector<vector<int>> dp(N + 1, vector<int>(V + 1, 0)); for (int i = 1; i <= N; i++) { // 枚举前i个物品 for (int j = 1; j <= V; j++) { // 枚举背包容量 if (j >= w[i - 1]) { // 状态转移：取 不放物品i 与 放入物品i 两种情况的最大值 // dp[i-1][j - w[i-1]] 确保每个物品最多使用一次（01背包核心） dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]); } else { // 容量不足，无法放入物品i dp[i][j] = dp[i - 1][j]; } } } // 输出：考虑所有N个物品，使用全部容量V时的最大价值 cout << dp[N][V]; return 0; } */// 版本2，因为上面的版本物品的重量和价值是从0开始存储的，所以i-1才是第i个物品的重量和价值// 如果将其从1开始存储，让下标i就是第i个物品，这样利于理解#include"bits/stdc++.h"usingnamespace std;intmain(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);int N, V; cin >> N >> V; vector<int>w(N +1,0),v(N +1,0);// 索引从1开始for(int i =1; i <= N; i++) cin >> w[i]>> v[i];// dp[i][j]: 考虑前i个物品，容量为j时的最大价值 vector<vector<int>>dp(N +1,vector<int>(V +1,0));for(int i =1; i <= N; i++){for(int j =1; j <= V; j++){if(j >= w[i]){// 当前容量能装下物品i// 选择放入或不放入的最大值// 注意：这里用dp[i-1][j-w[i]]，因为每个物品只能选一次 dp[i][j]=max(dp[i -1][j], dp[i -1][j - w[i]]+ v[i]);}else{// 容量不足 dp[i][j]= dp[i -1][j];}}} cout << dp[N][V];return0;}

DP解法2

dp[j]：容量为j时的最大价值

【疑惑】二维DP变一维DP到第发生了什么？ 【AI回答】

我们可以把您的困惑想象成以下几个层层递进的问题：

还有个地方要注意，在二维DP的时候，因为外层循环从1开始遍历的，所以第i个物品是i - 1，v[i - 1
但是一维DP是从0卡死机遍历的，所以第i个物品就是i，v[i]

第一层：数组含义变了，状态去哪了？

• 二维：dp[i][j]的 i和 j含义非常直观：i明确指向“前i个物品”，j是“容量”。
• 一维：dp[j]只剩下 j（容量）。最大的困惑来了：“前i个物品”这个维度消失了，它去哪了？
  • 答案：它被“当前正在遍历的是第几个物品”这个循环变量​ i 所隐含地代表了。dp[j]不再是一个静态的状态表，而是一个随着物品逐个处理，不断被覆盖、更新的“当前最优解数组”。

第二层：为什么可以“覆盖”？不会丢信息吗？

这是最核心的跳跃。关键在于理解“覆盖”的时机。

• 在处理第 i个物品时，dp[j]里存储的“旧值”，其实就是二维DP中 `dp[i-1][j] 的值。
• 我们需要用这个“旧值” (dp[i-1][j])，和“放入物品i”的可能性 (dp[i-1][j-w[i]]+v[i]) 做比较，得到“新值” (dp[i][j])。
• 一维DP的精髓：我们直接把计算出的“新值” (dp[i][j])，覆盖写回dp[j]这个位置。因为接下来要计算dp[i+1][*]，需要用到的就是dp[i][*]，而dp[i-1][*]已经不会再被用了，所以可以安全覆盖。

第三层：为什么必须逆序？正序到底哪里错了？

这是另一个关键困惑，也是01背包与完全背包的核心区别。

• 逆序（j = V; j >= w[i]; j--）：
  • 当计算 dp[j]时，它需要的 dp[j - w[i]]是还没被当前物品更新过的、真正的“旧值”（即dp[i-1][j-w[i]]）。
  • 这保证了在状态转移中，dp[j - w[i]] + v[i]代表的是“只在前i-1个物品里选，腾出空间后，再放入1个物品i”，符合01背包要求。
• 正序（j = w[i]; j <= V; j++）：
  • 当计算较大的 dp[j]时，它需要的 dp[j - w[i]]可能已经被当前物品i更新过了（即已经是dp[i][j-w[i]]）。
  • 那么 dp[j - w[i]] + v[i]的含义就变成了“在已经可能放过物品i的基础上，再放一个物品i”。这就相当于同一个物品被放了多次，变成了“完全背包”的解法。

第四层：如何形象地理解这个过程？

您可以想象一维数组 dp是一个“流水线”，每个物品 (i) 依次经过。

• 对于当前物品，工人从流水线尾部开始向前检查（逆序）。
• 工人检查位置 j：他看流水线当前记录（旧值，即不考虑本物品时的最优解），再对比“如果在本位置放入当前物品，需要查看前面 j-w[i]位置的记录（那还是旧值）+ 当前物品价值”哪个更大，然后把更大的结果更新到流水线的 j位置。
• 因为是从后往前干，当工人更新前面的位置时，后面位置依赖的“前面的记录”还是旧的，没有被动过。这就是逆序的妙处。

/* 【纯01背包问题-一维DP】 有N件物品和一个容量为V的背包。第i件物品的重量是`w[i]`，价值是`v[i]`。 求解将哪些物品装入背包可使这些物品的总重量不超过背包容量，且总价值最大。每种物品只能选择0个或1个。 【输入格式】 - 第一行：两个整数N和V，表示物品数量和背包容量 - 接下来N行：每行两个整数`w[i]`和`v[i]`，表示第i件物品的重量和价值 【输出格式】 - 一个整数，表示最大价值 Author：郑龙浩 Date：2026-02-28 用时： */#include"bits/stdc++.h"usingnamespace std;intmain(){int N, V; cin >> N >> V; vector<int>w(N),v(N);for(int i =0; i < N; i++){ cin >> w[i]>> v[i];}// 一维DP：dp[j] 表示容量为j时的最大价值 vector<int>dp(V +1,0);for(int i =0; i < N; i++){// 遍历每个物品// 必须从后往前遍历容量，确保每个物品只使用一次for(int j = V; j >= w[i]; j--){// 当容量j不足以放入物品i时，循环终止// 状态转移：取 不放入当前物品 与 放入当前物品 两种情况的最大值 dp[j]=max(dp[j], dp[j - w[i]]+ v[i]);}}// 输出：使用全部容量V时的最大价值 cout << dp[V]<< endl;return0;}