蓝桥杯“搬砖”题解：贪心排序与01背包的融合实战

1. 项目概述：从“搬砖”到“最优装载”的算法实战

最近在复盘蓝桥杯国赛的真题，2020年B组的“搬砖”这道题给我留下了挺深的印象。它初看像是个简单的体力活问题，但内核却融合了贪心排序和01背包这两个经典算法思想，是一道检验选手能否灵活运用基础算法解决复杂实际问题的好题。很多朋友在初次接触时，可能会直接套用01背包模板，结果发现答案不对，这就是忽略了问题中隐含的“顺序”约束。今天，我就结合自己的解题和教学经验，把这道题的核心思路、排序策略的推导、背包模型的转化以及编码实现中的坑点，掰开揉碎了讲清楚。无论你是正在备赛的蓝桥杯选手，还是想巩固动态规划与贪心算法的开发者，相信这篇都能给你带来直接的帮助。

简单来说，题目是这样的：给定一堆砖头，每块砖有自身的重量w_i和价值v_i。你需要选择一些砖，按照某种顺序搬走。关键的约束在于，对于你选择的砖块序列，每一块砖的重量必须不大于前面所有砖块重量之和（可以理解为你的承重能力在累加）。目标是在满足这个顺序约束的前提下，使得搬走砖块的总价值最大。这就像是一个逐渐成长的搬运工，开始力气小只能搬轻的，随着搬的砖越多（总重量越大），力气也越大，才能搬更重的砖。我们的任务就是找出能让这个“搬运工”收获最丰厚的搬砖方案。

2. 核心思路拆解：为什么贪心排序是破局关键

2.1 理解问题的双重约束

初次读题，我们识别出两个核心要素：选择（选哪些砖）和顺序（按什么顺序搬）。01背包算法擅长解决“选择”问题，在总重量限制下最大化价值。但经典的01背包问题不关心物品的放入顺序，因为背包的容量是固定的，先放后放不影响结果。

然而，本题的约束是动态的：当前砖的重量不能超过已搬砖的总重量。这意味着顺序直接影响可行性。例如，有两块砖，A(重量5，价值10)，B(重量10，价值20)。如果你先搬B，需要初始承重至少10，这要求你之前已经搬了足够多的砖，但一开始你并没有。如果先搬A，获得5的承重基础，就可以再搬B。所以，顺序决定了哪些砖块组合是可行的。

因此，解题框架必然是：先通过某种策略确定一个最优的搬运顺序（贪心排序），然后在这个顺序的约束下，决定最终选择哪些砖（01背包）。这里的“最优顺序”是指，对于任意一个最终被选中的砖块集合，都存在一种按此顺序排列的方式，使得约束得以满足，并且这个顺序能帮助我们简化后续的选择决策。

2.2 贪心排序策略的推导

如何排序？一个直观的想法是按重量升序，先搬轻的。这符合“从小积大”的直觉。但考虑价值和重量呢？比如砖块X(1, 100)和Y(100, 101)。按重量升序，X在Y前，这很好。但如果换一下，砖块A(5, 10)和B(6, 11)，仅仅按重量或价值排序都不够全面。

我们需要一个兼顾重量和价值的排序标准。这里引入一个关键的贪心策略：按照w_i + v_i升序排序。

我们来推导一下为什么这个策略有效。假设有两块砖i和j，在当前已搬总重量为S的前提下，都可以被搬（即w_i <= S且w_j <= S）。我们应该先搬哪一块，才能为后续留下更大的可能性？

考虑两种排列顺序：

1. 先i后j：需要满足w_i <= S且w_j <= S + w_i。
2. 先j后i：需要满足w_j <= S且w_i <= S + w_j。

已知S >= max(w_i, w_j)，所以两个顺序的第一条件都满足。关键在于第二条件。我们希望选择的顺序能让后续的可选砖块范围更广，即让S' = S + w_i + w_j之后的状态更灵活。但更重要的是，要确保在中间状态（搬完第一块时）也能满足第二块的条件。

比较两种顺序：

• 顺序1（i先）：要求w_j <= S + w_i
• 顺序2（j先）：要求w_i <= S + w_j

由于S是固定的，为了让顺序1比顺序2更容易满足（即更优），我们希望w_j <= S + w_i这个条件比w_i <= S + w_j更宽松。因为S相同，这等价于希望w_i相对w_j更大一些吗？并不完全。让我们消除S，考虑一个更强的条件：如果对于任意S，顺序1都优于顺序2，那么需要w_j - w_i <= w_i恒成立？这显然不对。

正确的推导需要交换论证法。假设在一个最优的搬砖序列中，存在相邻的两块砖i和j，且i在j之前，但是w_i + v_i > w_j + v_j。我们尝试交换它们的位置。

• 原顺序（... i, j ...）：需满足w_i <= S_prev和w_j <= S_prev + w_i。
• 新顺序（... j, i ...）：需满足w_j <= S_prev和w_i <= S_prev + w_j。 原顺序已知可行，所以w_j <= S_prev + w_i。新顺序的第一个条件w_j <= S_prev由原顺序i的条件w_i <= S_prev和w_i + v_i > w_j + v_j无法直接推出，但我们可以分析价值变化。更重要的是，我们可以证明，如果w_i + v_i > w_j + v_j，那么交换后，新顺序要么仍然可行，要么会得到一个不更差的解（通过调整）。一个常见且易于理解的结论是：按w_i + v_i升序排列，可以保证对于任意一个可行的选取集合，总能找到一个按此顺序排列的可行序列。因此，我们可以先按此规则对所有砖块进行排序，将“顺序”问题固化，进而转化为一个选择问题。

注意：这个排序规则是本题贪心部分最精妙也最容易出错的地方。务必理解，排序是为了给后续的DP创造无后效性的条件，而不是直接决定最终选择。最终选择哪些砖，还要靠背包来决定。

2.3 转化为01背包模型

对所有砖块按w_i + v_i升序排序后，“顺序”约束就巧妙地转化为了一个类似于背包的“容量”约束。设dp[j]表示考虑完前i块砖（排序后），当前已搬砖总重量恰好为j时，所能获得的最大总价值。

为什么是“恰好为”j？因为本题的动态约束是“当前砖重量 ≤ 当前总重量”。如果我们用传统的“不超过j”的定义，在状态转移时，无法准确判断当前砖w_i是否小于等于已选砖的真实总重量。而使用“恰好为j”，则j精确代表了已选砖的总重量，那么判断条件w_i <= j就非常直接且正确。

状态转移方程与01背包类似，但多了一个前置条件： 对于第i块砖（重量w_i, 价值v_i）： 如果w_i <= j，则dp[j] = max(dp[j], dp[j - w_i] + v_i)否则，不能选择该砖块。

这里j的枚举范围上限是多少？显然，是所有砖块重量之和sum_w。但我们可以进行优化，因为题目可能给出总重上限，或者我们只关心最大价值，通常枚举到sum_w即可。

最终答案是什么？不是dp[sum_w]，因为不一定非要搬完所有砖。答案是所有dp[j] (0 <= j <= sum_w)中的最大值。因为dp[j]代表了总重量恰好为j时的最大价值，我们需要遍历所有可能的最终总重量，来找出价值最大的那个方案。

3. 算法实现与细节剖析

3.1 数据结构定义与输入处理

首先，我们需要定义砖块的结构体，并处理输入。

#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int MAXN = 1005; // 根据题目数据范围设定，例如N最大1000 const int MAXM = 20005; // 重量上限，例如总重最大20000 struct Brick { int w; // 重量 int v; // 价值 int sum; // w+v，用于排序 } bricks[MAXN]; int dp[MAXM]; // dp数组，dp[j]表示总重量恰好为j时的最大价值 int main() { int n; cin >> n; int total_weight = 0; for (int i = 1; i <= n; ++i) { cin >> bricks[i].w >> bricks[i].v; bricks[i].sum = bricks[i].w + bricks[i].v; total_weight += bricks[i].w; // 计算总重，作为背包容量上限 } // ... 后续代码 }

处理要点：

1. 数组大小：MAXM是背包容量（总重量）的上限，需要根据题目数据范围估算。如果题目未明确，通常取N * max(w_i)或直接设一个足够大的数（如20000）。
2. 索引从1开始：个人习惯让数据从索引1开始存储，便于思考和调试，与日常认知一致。
3. 计算总重：total_weight用于确定DP循环的上限，避免无效计算。

3.2 贪心排序的实现

排序是贪心思想的直接体现。

// 按照 w+v 升序排序 bool cmp(const Brick& a, const Brick& b) { // 如果 w+v 相等，可以按重量或价值二次排序，但通常不影响结果 // 这里我们按重量升序二次排序，使序列更确定 if (a.sum != b.sum) return a.sum < b.sum; return a.w < b.w; // 次要关键字，重量小的在前 } // 在输入之后，DP之前调用 sort(bricks + 1, bricks + n + 1, cmp);

为什么需要次要排序关键字？当w_i + v_i相等时，理论上任何顺序都满足贪心推导。但为了代码结果的确定性和避免一些边界疑虑，增加一个次要排序规则（如按w升序）是良好的编程习惯。这确保了相同sum的砖块有一个固定的顺序，不影响DP的正确性。

3.3 动态规划过程详解

这是整个算法的核心。我们需要初始化DP数组，并进行状态转移。

// 初始化DP数组 memset(dp, -0x3f, sizeof(dp)); // 初始化为负无穷，表示不可达状态 dp[0] = 0; // 没有搬任何砖时，总重量为0，价值为0，是合法起点 // 01背包DP过程 for (int i = 1; i <= n; ++i) { int w = bricks[i].w; int v = bricks[i].v; // 倒序枚举重量！这是01背包空间优化的关键。 for (int j = total_weight; j >= w; --j) { // 关键判断：只有当前总重量 j 大于等于砖块重量 w 时，才能考虑放入 // 注意，我们的dp[j]定义是“恰好重量为j”，所以判断条件是 w <= j，并且 dp[j-w] 必须是一个可达状态 // 由于我们初始化为负无穷，只有可达状态其值才非负（或大于初始负值） if (dp[j - w] != -0x3f) { // 如果前一个状态可达 dp[j] = max(dp[j], dp[j - w] + v); } } } // 寻找最大价值 int ans = 0; for (int j = 0; j <= total_weight; ++j) { ans = max(ans, dp[j]); } cout << ans << endl;

逐行解析与避坑指南：

1. 初始化dp为负无穷：这是“恰好型”背包问题的标准初始化。dp[0]=0表示不选任何砖是合法的。负无穷表示该总重量状态无法通过选取砖块达到。如果不这样初始化，dp数组默认全0，那么dp[j]就可能从一些非法的、重量未恰好凑成的状态转移过来，导致错误。例如，dp[5]初始为0，但可能根本没有方案能使总重量恰好为5，这个0就是错误的。
2. 倒序枚举j：这是01背包空间优化（一维数组）的经典写法。正序枚举会导致同一块砖被重复使用多次（变成完全背包）。务必牢记：一维数组、01背包、倒序枚举。
3. 条件判断if (dp[j - w] != -0x3f)：这个判断至关重要。它确保了状态转移只能从可达的、有效的前驱状态发生。dp[j-w]如果是负无穷，意味着不存在一种方案使得总重量恰好为j-w，那么从该状态加上砖块i得到重量j的方案也是无效的，不应该更新dp[j]。
4. 状态转移方程dp[j] = max(dp[j], dp[j - w] + v)：标准的01背包价值更新。dp[j]是不选当前砖，dp[j-w] + v是选当前砖。
5. 最终答案遍历：由于dp[j]是恰好重量为j的最大价值，最优解可能对应不同的总重量，所以需要遍历所有j取最大值。

3.4 一个完整的代码示例与测试

将以上部分组合起来，并提供一个简单的测试用例。

#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int MAXN = 1005; const int MAXM = 20005; struct Brick { int w, v, sum; } bricks[MAXN]; int dp[MAXM]; bool cmp(const Brick& a, const Brick& b) { if (a.sum != b.sum) return a.sum < b.sum; return a.w < b.w; } int main() { int n; cin >> n; int total_weight = 0; for (int i = 1; i <= n; ++i) { cin >> bricks[i].w >> bricks[i].v; bricks[i].sum = bricks[i].w + bricks[i].v; total_weight += bricks[i].w; } sort(bricks + 1, bricks + n + 1, cmp); memset(dp, -0x3f, sizeof(dp)); dp[0] = 0; for (int i = 1; i <= n; ++i) { int w = bricks[i].w; int v = bricks[i].v; for (int j = total_weight; j >= w; --j) { if (dp[j - w] != -0x3f) { // 确保前驱状态有效 dp[j] = max(dp[j], dp[j - w] + v); } } } int ans = 0; for (int j = 0; j <= total_weight; ++j) { ans = max(ans, dp[j]); } cout << ans << endl; return 0; }

测试用例： 输入：

5 4 3 3 5 6 6 2 4 5 7

手动计算（按w+v排序后）：

1. 排序后砖块：(2,4,6), (3,5,8), (4,3,7), (5,7,12), (6,6,12)。注意(5,7)和(6,6)的sum都是12，按重量二次排序。
2. DP过程（简述）：
   • 考虑(2,4)：可达成状态 dp[2]=4。
   • 考虑(3,5)：从dp[2]=4可达dp[5]=9；自身dp[3]=5。
   • 考虑(4,3)：从dp[2]=4可达dp[6]=7；从dp[3]=5可达dp[7]=8；从dp[5]=9可达dp[9]=12。
   • ... 以此类推。
3. 最终遍历dp数组，找到最大价值。可以验证，最优解是选择(2,4), (3,5), (5,7)，总重10，总价值16。顺序是2,3,5（满足w_i <= 已搬总重）。

4. 常见问题与深度思考

4.1 为什么不能直接用重量升序排序？

这是最常见的误区。我们构造一个反例： 砖块A: (重量1, 价值100) 砖块B: (重量100, 价值101) 砖块C: (重量101, 价值1)

按重量升序：A(1,100), B(100,101), C(101,1) 如果只按此顺序做背包，可能会先选A，然后因为B的重量100 > 已选总重1，无法选B。但实际上，最优解可能就是只选B（价值101）或者只选A（价值100）。然而，如果我们按w+v排序： A: sum=101 B: sum=201 C: sum=102 排序后：A(1,100), C(101,1), B(100,101) 在这个顺序下，DP可以考虑到先选B的方案（当j>=100时，dp[100]可以直接被B更新为101）。而按重量排序时，B出现在A之后，DP过程会受到A是否被选的影响，可能无法独立考虑B的优解。w+v排序更好地平衡了重量和价值对“后续容纳能力”的影响。

4.2 DP数组容量上限的优化

我们的total_weight是所有砖块重量之和，在最坏情况下（如1000块砖，每块重1000），容量需要开到1e6，对于C++来说，int dp[1000005]在全局区可能没问题，但占用空间较大。如果题目内存限制严格，可以考虑以下优化：

1. 滚动数组：我们已经使用了一维数组，这是空间上的最优解（O(容量)）。
2. 容量上界剪枝：在DP过程中，实时维护当前能达到的最大重量max_j。内层循环for (int j = max_j; j >= w; --j)，而不是每次都从total_weight开始。这能减少大量无效计算。

int max_j = 0; // 当前可达的最大重量 dp[0] = 0; for (int i = 1; i <= n; ++i) { int w = bricks[i].w; int v = bricks[i].v; // 从当前可达的最大重量开始倒序枚举，注意下界是w for (int j = max_j + w; j >= w; --j) { // 需要确保 j-w 不超过之前的 max_j，但因为我们从 max_j+w 开始往下，j-w 自然 <= max_j // 更安全的写法是分别判断 if (j - w <= max_j && dp[j - w] != -0x3f) { dp[j] = max(dp[j], dp[j - w] + v); } } // 更新当前可达的最大重量 max_j += w; // 注意，这是理论上可达的最大值，实际可能有些j达不到 // 更精确的更新可以在循环后遍历，但通常这样近似也可以 }

注意：这种优化需要小心处理边界，确保j-w索引有效。在竞赛中，如果时间允许，直接开足够大的数组更稳妥。

4.3 如果砖块数量极大（例如N=10^5）怎么办？

上述算法的时间复杂度是 O(N * total_weight)。如果N很大，且单个重量也很大，total_weight会非常大，导致DP循环无法进行。这时，经典的01背包算法就不再适用。

对于这种大规模问题，题目通常会：

1. 改变约束条件（如总重量限制很小）。
2. 或者，需要用到贪心或其他优化技巧（如价值很小可以考虑对价值做DP）。
3. 本题的特定约束（w_i <= sum_of_selected）可能具有更特殊的性质，可以推导出贪心选择策略（例如，按价值密度v_i/w_i排序？但需要证明）。但在标准的2020蓝桥杯国赛题设下，N通常在10^3量级，总重也在10^4量级，O(N*M)的DP是可行的。

4.4 如何输出具体方案？

有时我们不仅需要知道最大价值，还想知道是哪些砖块构成了这个最优解。这需要我们在DP过程中记录“选择”的路径。

// 使用一个二维数组或vector记录前驱状态 int pre[MAXN][MAXM]; // pre[i][j] 表示状态dp[i][j]是否选择了第i块砖 // 或者，在一维数组下，使用单独的选择记录数组，但需要倒推，更复杂。 // 更实用的方法：在DP完成后，从最终状态倒推。 int cur_weight = -1; int max_val = 0; for (int j = 0; j <= total_weight; ++j) { if (dp[j] > max_val) { max_val = dp[j]; cur_weight = j; // 记录达到最大价值时的总重量 } } // 倒推找出选了哪些砖 vector<int> selected; for (int i = n; i >= 1 && cur_weight > 0; --i) { int w = bricks[i].w; int v = bricks[i].v; // 判断第i块砖是否被选中 // 条件： cur_weight >= w 且 dp[cur_weight] 是由 dp[cur_weight - w] + v 转移而来 // 由于我们只有最终结果，没有记录路径，需要额外信息。 // 因此，在DP时，最好用二维数组，或者用一维数组但另开一个path数组记录决策。 } // 二维DP记录路径的示例（未优化空间）： int dp[MAXN][MAXM]; bool choose[MAXN][MAXM]; // 记录是否选择 for (int i = 1; i <= n; ++i) { for (int j = 0; j <= total_weight; ++j) { dp[i][j] = dp[i-1][j]; // 不选 choose[i][j] = false; if (j >= w[i] && dp[i-1][j - w[i]] != -INF) { if (dp[i-1][j - w[i]] + v[i] > dp[i][j]) { dp[i][j] = dp[i-1][j - w[i]] + v[i]; choose[i][j] = true; } } } } // 倒推 int j = cur_weight; for (int i = n; i >= 1; --i) { if (choose[i][j]) { selected.push_back(i); j -= w[i]; } } reverse(selected.begin(), selected.end());

输出方案会增加空间和时间开销，但有助于调试和理解DP过程。

5. 算法扩展与变式思考

5.1 如果约束条件变为“当前砖重量必须严格小于之前总重”？

原题是“小于等于”。如果改为“严格小于”，即w_i < S_prev，那么我们的排序策略和DP判断条件需要微调吗？

排序策略w_i + v_i可能依然有效，但需要更严谨的证明。在DP转移的判断条件上，需要将if (w_i <= j)改为if (w_i < j)。因为j代表已选砖的总重量，对于当前要选的砖i，其重量必须严格小于已选总重j（注意，j是前i-1块砖决策后的总重，即S_prev）。这个改动很小，但体现了对问题条件细节的准确把握。

5.2 如果每块砖还有“搬动时间”或“冷却时间”？

这会将问题引向更复杂的调度或带时间窗口的背包问题。例如，搬砖需要时间t_i，并且搬砖过程中有一个总时间限制T。那么状态可能需要增加一维时间：dp[j][t]表示总重量恰好为j、总时间恰好为t时的最大价值。这变成了一个二维费用的背包问题，复杂度会上升。

5.3 与“工作调度（带截止时间和利润）”问题的联系

这是一个经典的贪心问题：有N项工作，每项工作有截止时间d_i和利润p_i，每个时间点只能做一项工作，问如何安排获得最大利润。通常解法是按利润降序排序，然后为每个工作寻找不晚于其截止时间的空闲时段。

“搬砖”问题与其有相似之处：都有“顺序”约束（搬砖的重量约束 vs 工作的截止时间约束）和最大化目标。但区别在于，搬砖的约束是累积性的（当前重量≤累积重量），而工作调度是时间点性的。不过，它们都体现了贪心排序结合后续选择的解题范式。理解这种联系有助于构建算法思维。

5.4 贪心排序正确性的再思考

我们用了w_i + v_i排序，但为什么不是v_i / w_i（价值密度）或者w_i单独排序？这源于问题特定的约束条件w_i <= S。我们可以尝试交换论证：假设最优解中相邻的两块砖i和j顺序不是按w+v升序。通过交换它们，并证明交换后要么仍然可行且总价值不降，要么可以调整得到不更差的解。这个证明的关键点在于，约束w_j <= S + w_i和w_i <= S + w_j的比较，以及交换对总价值的影响。w+v作为一个整体，恰好能在比较中平衡重量和价值的影响。很多竞赛题解和论文中都有严谨的数学证明，对于应试和解题，记住这个结论并理解其直观意义（平衡重量对后续的限制和价值的贡献）更为高效。

6. 实战调试与性能分析

6.1 使用小数据测试边界情况

在编写完代码后，务必用多种小数据测试，特别是边界情况：

1. 只有一块砖：输入1\n w v，检查输出是否为v。
2. 所有砖都太重：比如第一块砖重量就为100，后面都是1。检查程序是否能正确处理无法选择任何砖（除了第一块）的情况。
3. 重量为0的砖：如果题目允许重量为0，我们的判断条件w_i <= j在j=0时，对于w_i=0的砖是成立的。DP需要能处理这种情况。注意，初始化dp[0]=0，当w_i=0时，dp[j] = max(dp[j], dp[j] + v_i)，这会导致dp[0]被重复加多次？因为j从total_weight倒序到0，当j=0时，dp[0] = max(dp[0], dp[0] + v_i)，如果v_i>0，dp[0]会不断增加。这相当于一块重量为0但价值为正的砖可以无限次被选，这不符合01背包“每个物品最多选一次”的规则。因此，如果存在重量为0的物品，需要特殊处理，或者确保在DP中每个物品只被考虑一次。在我们的循环中，由于是倒序，对于w_i=0，j从total_weight到0，dp[j]会不断用dp[j] + v_i更新自己，实际上只会在第一次更新时生效（因为dp[j]在更新前是旧值），后续的j不会重复使用本次的更新结果。但为了清晰，可以特判w_i==0的情况，按01背包逻辑，重量为0的物品选不选只影响价值，可以单独处理。

6.2 时间复杂度与空间复杂度分析

• 时间复杂度：排序O(N log N)+ DPO(N * total_weight)。其中DP是主要部分。
• 空间复杂度：使用一维DP数组，O(total_weight)。

对于蓝桥杯的环境，通常N <= 1000,total_weight <= 20000，那么N * total_weight ≈ 2e7，在C++中是可以接受的（约2千万次操作）。如果total_weight更大，接近1e5，操作次数达到1e8，就可能需要优化或考虑其他算法。

6.3 内存与初始化技巧

• memset(dp, -0x3f, sizeof(dp))：将数组初始化为一个很大的负数（约 -0x3f3f3f3f）。使用-1或0初始化有时会与合法价值混淆（比如价值可能为0）。用负无穷可以清晰表示不可达状态。
• 数组大小：dp数组大小是MAXM，MAXM应略大于total_weight的最大可能值。全局数组开在静态存储区，大小限制较宽松（通常几MB到几十MB）。如果开到局部变量（栈上），大数组会导致栈溢出。

7. 总结与个人心得

这道“搬砖”题之所以经典，在于它完美地将两个基础算法（贪心、01背包）结合，并设置了一个容易让人忽略的排序前提。我最初做的时候也栽在了直接套用背包模板上。后来明白，面对复杂约束，分解问题是关键：先解决顺序（贪心排序），再解决选择（动态规划）。这种“先排序后DP”的思路，在其他问题中也能见到，例如一些带时间顺序的背包问题。

在实现时，有两个细节让我印象深刻：一是“恰好型”背包的初始化，必须用负无穷标记不可达状态；二是DP前的排序规则，w_i + v_i这个式子需要理解其背后的贪心思想，而不是死记硬背。多构造几个反例，有助于加深理解。

最后，对于算法学习，我的体会是：刷题不在多，而在精。像这样一道题，彻底搞懂它的每一步为什么这么做，比模糊地做十道题更有用。自己手动模拟DP表格，尝试修改条件（比如把<=改成<），思考如果数据范围变化该如何应对，这样才能真正把知识变成解决新问题的能力。蓝桥杯的题目往往就是这样，考察的是对基础算法的灵活运用和组合能力，把这道题吃透，你对贪心和背包的理解一定能上一个台阶。