信息学奥赛 1267题：01背包问题 3种解法（DP/DFS/记忆化）性能实测对比

信息学奥赛1267题：01背包问题三种解法深度评测与实战指南

背包问题作为动态规划的经典案例，一直是算法竞赛和面试中的高频考点。今天我们将以信息学奥赛1267题为例，全面剖析01背包问题的三种解法——动态规划、深度优先搜索和记忆化搜索，并通过实测数据对比它们的性能差异。无论你是正在备战信息学奥赛的选手，还是准备技术面试的求职者，这篇文章都将为你提供清晰的解题思路和实用的性能优化建议。

1. 01背包问题核心解析

01背包问题的基本描述是：给定一个容量为M的背包和N件物品，每件物品有重量w和价值v，要求在不超过背包容量的前提下，选择物品使得总价值最大。这里的"01"意味着每件物品要么完整放入背包（1），要么完全不放入（0），不能分割。

这个问题看似简单，却蕴含着深刻的算法思想。理解它的多种解法不仅能帮助我们应对竞赛题目，更能培养解决复杂优化问题的思维能力。在实际应用中，类似的问题场景比比皆是——从资源分配到投资组合选择，其核心都是如何在有限条件下做出最优决策。

让我们先明确问题的数学表达：

• 输入：背包容量M，物品数量N，每个物品的重量w[i]和价值v[i]（1≤i≤N）
• 输出：在Σw[i]≤M的前提下，最大化Σv[i]

三种解法的核心差异在于解决问题的思路：

1. 动态规划(DP)：自底向上构建解，通过状态转移方程逐步求解
2. 深度优先搜索(DFS)：暴力枚举所有可能的组合，保留最大值
3. 记忆化搜索：在DFS基础上加入缓存，避免重复计算

2. 动态规划解法详解

动态规划是解决背包问题最高效的方法之一，其核心在于状态定义和转移方程的建立。对于01背包问题，我们通常采用二维状态表示：

dp[i][j] // 表示考虑前i个物品，背包容量为j时的最大价值

状态转移方程基于一个简单的决策：对于第i个物品，我们有两种选择：

• 不放入：价值保持为dp[i-1][j]
• 放入（如果j≥w[i]）：价值变为dp[i-1][j-w[i]] + v[i]

取两者的最大值即为当前状态的最优解：

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

2.1 基础二维DP实现

以下是标准的二维DP实现代码：

#include <bits/stdc++.h> using namespace std; #define N 35 #define M 250 int dp[N][M], w[N], v[N]; int main() { int m, n; cin >> m >> n; // m为背包容量，n为物品数量 for(int i = 1; i <= n; ++i) cin >> w[i] >> v[i]; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { if(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][m]; return 0; }

2.2 空间优化：滚动数组

观察状态转移方程可以发现，dp[i][]只依赖于dp[i-1][]，因此我们可以将空间复杂度从O(NM)优化到O(M)：

int dp[M], w[N], v[N]; int main() { int m, n; cin >> m >> n; for(int i = 1; i <= n; ++i) cin >> w[i] >> v[i]; for(int i = 1; i <= n; ++i) { for(int j = m; j >= w[i]; --j) { // 注意倒序遍历 dp[j] = max(dp[j], dp[j-w[i]] + v[i]); } } cout << dp[m]; return 0; }

关键点：内层循环必须倒序遍历，确保在计算dp[j]时，dp[j-w[i]]还未被当前物品更新，相当于仍然保存着i-1时的状态值。

3. 深度优先搜索解法

虽然动态规划效率高，但深度优先搜索(DFS)能帮助我们更直观地理解问题的解空间。DFS通过递归枚举所有可能的物品组合，保留价值最大的解。

3.1 基本DFS实现

#include <bits/stdc++.h> using namespace std; int m, n, maxVal; int w[35], v[35]; void dfs(int idx, int currentWeight, int currentValue) { if(idx > n) { if(currentWeight <= m && currentValue > maxVal) maxVal = currentValue; return; } // 不选当前物品 dfs(idx + 1, currentWeight, currentValue); // 选当前物品（如果不超过容量） if(currentWeight + w[idx] <= m) { dfs(idx + 1, currentWeight + w[idx], currentValue + v[idx]); } } int main() { cin >> m >> n; for(int i = 1; i <= n; ++i) cin >> w[i] >> v[i]; dfs(1, 0, 0); cout << maxVal; return 0; }

3.2 DFS的性能分析

DFS的时间复杂度为O(2^N)，因为每个物品都有选或不选两种可能。当N=30时，2^30≈10^9，这在竞赛中通常会超时。因此，纯DFS只适用于非常小的数据规模（N≤20）。

4. 记忆化搜索解法

记忆化搜索是DFS的优化版本，通过记录已经计算过的状态来避免重复计算。对于背包问题，我们可以用二维数组memo[i][j]记录考虑前i个物品、剩余容量为j时的最大价值。

4.1 记忆化搜索实现

#include <bits/stdc++.h> using namespace std; #define N 35 #define M 250 int w[N], v[N], memo[N][M]; int dfs_memo(int idx, int remaining) { if(idx > n) return 0; if(memo[idx][remaining] != -1) return memo[idx][remaining]; int maxVal = dfs_memo(idx + 1, remaining); // 不选 if(remaining >= w[idx]) { int select = v[idx] + dfs_memo(idx + 1, remaining - w[idx]); if(select > maxVal) maxVal = select; } return memo[idx][remaining] = maxVal; } int main() { cin >> m >> n; for(int i = 1; i <= n; ++i) cin >> w[i] >> v[i]; memset(memo, -1, sizeof(memo)); cout << dfs_memo(1, m); return 0; }

4.2 记忆化搜索与DP的关系

记忆化搜索实际上是动态规划的递归实现，两者有着相同的时间复杂度O(NM)。区别在于：

• DP是自底向上迭代
• 记忆化搜索是自顶向下递归

在竞赛中，当状态转移比较复杂或维度较多时，记忆化搜索往往更易于实现和调试。

5. 三种解法性能实测对比

为了直观比较三种解法的效率，我们在相同环境下（G++ 9.4.0，-O2优化）对N=30，M=200的数据规模进行了测试：

测试数据：随机生成30个物品，重量w[i]∈[1,50]，价值v[i]∈[1,100]，背包容量M=200

从测试结果可以看出：

1. 动态规划（尤其是一维优化版本）在时间和空间上都是最优的
2. 记忆化搜索性能接近二维DP，但因递归调用有额外开销
3. DFS在N=30时完全不可行

6. 解法选择决策指南

在实际解题或竞赛中，如何选择合适的解法？以下决策树可以帮助你快速判断：

是否N≤20？ ├─ 是 → 可以使用DFS，代码简单不易错 └─ 否 → 需要使用DP或记忆化搜索 ├─ 是否需要打印具体方案？ │ ├─ 是 → 二维DP，便于回溯 │ └─ 否 → 一维DP，空间效率高 └─ 状态转移是否复杂？ ├─ 是 → 记忆化搜索更易实现 └─ 否 → 直接使用DP

对于信息学奥赛1267题（N≤30，M≤200），强烈推荐使用一维动态规划，它在代码简洁性、运行效率和空间使用上都达到了最佳平衡。

7. 常见优化技巧与边界处理

在实际编码中，有几个细节需要注意：

1. 数组大小：通常比题目给出的最大限制稍大一些（如+10）
2. 初始化：dp[0][j]和dp[i][0]都应初始化为0
3. 输入优化：对于大规模数据，使用更快的输入方式
4. 负数处理：如果允许负重量或价值，需要特殊处理

// 快速输入模板（适用于大量数据） inline int read() { int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } // 在主函数中使用： m = read(); n = read(); for(int i = 1; i <= n; ++i) { w[i] = read(); v[i] = read(); }

8. 扩展与变式练习

掌握基础01背包后，可以尝试以下变种问题：

• 完全背包：物品可以取无限次
• 多重背包：物品有数量限制
• 分组背包：物品属于不同的组，每组只能选一个
• 依赖背包：物品之间存在依赖关系

每种变种都有对应的状态定义和转移方程调整，但核心思想与01背包一脉相承。例如，完全背包的一维DP实现只需将内层循环改为正序：

for(int i = 1; i <= n; ++i) { for(int j = w[i]; j <= m; ++j) { // 正序遍历 dp[j] = max(dp[j], dp[j-w[i]] + v[i]); } }

理解01背包问题的多种解法不仅能帮助我们在竞赛中取得好成绩，更重要的是培养了将复杂问题分解、寻找最优子结构的思维能力。在实际编程中，我习惯先用记忆化搜索验证思路正确性，再转化为更高效的一维DP实现。当遇到特别大的数据规模时，还可以考虑进一步优化，如使用位运算压缩状态或基于贪心的近似算法。