当前位置：首页 > news >正文

LeetCode 594题‘磁带利用率’详解：从背包DP到贪心交换，附C++完整代码与三大易错点

news 2026/4/20 6:13:59

LeetCode 594题‘磁带利用率’深度解析：从动态规划到贪心策略的实战指南

当你面对LeetCode 594这道关于磁带利用率的问题时，是否曾困惑于如何将实际问题转化为算法模型？这道题表面看似简单，实则暗藏多个陷阱，需要我们对背包问题和贪心算法有深入理解才能完美解决。本文将带你从题目本质出发，逐步拆解两种核心解法，并揭示那些容易导致WA（Wrong Answer）的关键细节。

1. 题目理解与建模

题目描述：给定n个程序及其占用的磁带长度a[i]，以及磁带的总容量m。要求选择尽可能多的程序装入磁带，且在程序数量相同的情况下，使磁带利用率最高（即已用空间尽可能大）。

关键建模点：

这是一个典型的双目标优化问题：首要目标是最大化程序数量，次要目标是最大化磁带利用率
可以转化为0-1背包问题的变种：每个程序相当于物品，磁带容量是背包容量
与传统背包不同，我们需要同时跟踪两个指标：程序数量和已用空间

注意：题目中的"磁带利用率"实际包含两个维度——程序数量和空间利用率，这导致状态转移时需要特殊处理

2. 动态规划解法详解

2.1 DP状态设计

我们需要设计一个能同时记录程序数量和空间利用率的状态结构：

struct Node { int count; // 存储的程序数量 int sum; // 占用的磁带长度 vector<int> path; // 存储的程序路径（可选） }; Node dp[MAX_CAPACITY]; // dp数组

状态转移核心逻辑：

当考虑程序i时，对于每个可能容量j（从m到a[i]递减）：
- 比较加入程序i后的状态与当前状态
- 优先比较程序数量，数量多的更优
- 数量相同时，选择sum更大的方案

2.2 完整DP代码实现

#include <bits/stdc++.h> using namespace std; const int N = 1e4 + 5; struct Node { int count = 0; int sum = 0; vector<int> path; }; int main() { int n, m; cin >> n >> m; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; vector<Node> dp(m + 1); // 逆序处理程序 for (int i = n - 1; i >= 0; i--) { // 逆序处理容量 for (int j = m; j >= a[i]; j--) { int new_count = dp[j - a[i]].count + 1; int new_sum = dp[j - a[i]].sum + a[i]; // 状态转移条件 if (new_count > dp[j].count || (new_count == dp[j].count && new_sum >= dp[j].sum)) { dp[j].count = new_count; dp[j].sum = new_sum; dp[j].path = dp[j - a[i]].path; dp[j].path.push_back(a[i]); } } } cout << dp[m].count << " " << dp[m].sum << endl; // 输出路径（如果需要） for (int i = dp[m].path.size() - 1; i >= 0; i--) { cout << dp[m].path[i] << " "; } return 0; }

2.3 三大易错点解析

遍历顺序错误：
- 必须采用逆序处理容量（j从m到a[i]）
- 错误示例：for(int j = a[i]; j <= m; j++)会导致程序被重复选择
状态转移条件不完整：
- 必须同时考虑count和sum两个维度
- 常见错误：只比较count或只比较sum
等于情况的处理：
- 当count相同时，必须正确处理sum的比较
- 错误示例：if(new_count == dp[j].count && new_sum > dp[j].sum)漏掉了等于情况

3. 贪心算法优化解法

当程序总大小不超过磁带容量时，直接选择所有程序即可。否则，可以采用贪心策略：

初始选择：将程序按大小升序排列，尽可能多地选择小程序
交换优化：尝试用未选中的小程序替换已选中的大程序，提高利用率

3.1 贪心算法实现步骤

vector<int> solveGreedy(vector<int>& a, int m) { sort(a.begin(), a.end()); int total = accumulate(a.begin(), a.end(), 0); // 情况1：全部程序可以装入 if (total <= m) return { (int)a.size(), total }; // 情况2：需要选择部分程序 int sum = 0, count = 0; vector<bool> selected(a.size(), false); // 优先选择小程序 for (int i = 0; i < a.size(); i++) { if (sum + a[i] <= m) { sum += a[i]; count++; selected[i] = true; } else { break; } } // 尝试交换优化 int left = 0, right = a.size() - 1; while (left < count && right >= count) { int diff = a[right] - a[left]; if (sum + diff <= m) { sum += diff; selected[left] = false; selected[right] = true; left++; right--; } else { break; } } // 统计最终结果 int final_sum = 0, final_count = 0; vector<int> result; for (int i = 0; i < a.size(); i++) { if (selected[i]) { final_sum += a[i]; final_count++; result.push_back(a[i]); } } return { final_count, final_sum }; }

3.2 贪心与DP的对比分析

特性	动态规划解法	贪心解法
时间复杂度	O(n*m)	O(nlogn)
空间复杂度	O(m)	O(n)
最优解保证	总能得到最优解	可能不是最优解
适用场景	通用场景	程序大小差异明显时效果好
实现难度	中等	相对简单

4. 实战调试技巧与面试要点

4.1 常见调试场景

边界条件测试：
- 磁带容量为0
- 所有程序大小相同
- 单个程序大小等于磁带容量

特殊数据测试：

# 测试用例1：所有程序都能装入 n = 3, m = 10, a = [2, 3, 4] # 应输出3 9 # 测试用例2：需要选择 n = 4, m = 10, a = [2, 3, 4, 6] # 应输出3 9 # 测试用例3：临界情况 n = 5, m = 15, a = [1, 2, 3, 4, 5] # 应输出5 15