二分查找与贪心算法实战：求解华为OD机试“统一限载货物数最小值”问题

1. 项目概述：从一道华为OD机试真题说起

最近在帮几个准备华为OD机试的朋友做模拟练习，发现“统一限载货物数最小值”这道题出现的频率相当高，而且它确实是个“纸老虎”——乍一看题目描述有点绕，但一旦理解了背后的核心思想，用几种主流语言实现起来都不算复杂。这道题本质上是一个在特定约束下求最值的经典问题，非常考验对二分查找和贪心验证这两种基础算法的综合运用能力。很多朋友卡壳，往往不是因为算法本身多难，而是没把题目中的“货物”、“货车”、“限载”这些生活化描述，准确地翻译成计算机能处理的数学模型。

简单来说，题目给你一堆重量各不相同的货物（一个数组），以及若干辆容量完全相同的货车。你的任务是：找到那个最小的货车容量，使得用这些货车，能够在最多两趟内，把所有货物运完，并且每辆货车每趟装载的货物总重量不能超过其容量。这里的“最多两趟”是个关键约束，它让问题从简单的“装包”变成了需要分批次规划的调度问题。我见过不少Java选手一上来就想用动态规划硬解，结果复杂度爆炸；也见过Python新手试图用暴力枚举所有分配方案，显然不现实。其实，最优解往往藏在最基础的算法组合里。

接下来，我会彻底拆解这道题，不仅给出Java、C、C++、Python四种语言的代码实现，更重要的是，我会分享如何一步步分析问题、建立模型、选择算法、编码实现以及调试避坑的完整思考过程。无论你擅长哪种语言，或者正在为类似的机试题发愁，相信这篇从实战中总结的经验，都能给你带来直接的帮助。

2. 问题核心与数学模型拆解

2.1 题意转化与关键约束分析

首先，我们必须把口语化的题目描述，翻译成严谨的数学和逻辑语言。这是解决任何算法题的第一步，也是最容易出错的一步。

原题描述通常类似这样：有一批货物，其重量列表为weights = [w1, w2, ..., wn]。有k辆相同的货车。每辆货车有一个统一的载重上限limit。所有货物需要被运走，且每辆货车最多只能使用两次（即最多跑两个来回）。问：在能够运完所有货物的前提下，这个统一的载重上限limit最小是多少？

我们来逐条拆解其中的约束条件：

1. 统一限载：所有货车的最大载重量相同，记为limit。这是我们要求解的目标。
2. 货物不可分割：每个货物是一个整体，不能拆开运输。
3. 货车使用次数限制：每辆货车最多被使用两次。这意味着，在运输规划中，一辆车可以运一趟，也可以运两趟，但不能超过两趟。这是本题区别于普通装箱问题的核心。
4. 目标函数：寻找满足上述所有约束的最小limit。

一个常见的误解是：有k辆车，每辆车最多运两趟，那么是不是总共有2k个“运输槽位”？然后就把问题看成是普通的装箱问题？不对。因为一辆车如果第一趟没装满，它还可以跑第二趟，这两趟的载重之和不能简单叠加，它们共享同一个limit约束，但时间是分开的。更准确的建模方式是：我们需要将货物列表划分到最多2k个组中（因为每辆车最多贡献两个“趟次组”），并且每个组的货物总重量不得超过limit。

所以，问题的数学模型可以定义为：给定数组weights（正整数），整数k，寻找最小的正整数limit，使得能够将weights划分成不超过2k个子集，每个子集的元素和不超过limit。

2.2 算法选型：为什么是二分答案+贪心验证？

明确了模型，接下来就是选择算法。求“最小满足条件的值”，且这个值存在一个明确的边界（limit至少不小于最重单件货物，最多不超过货物总和），这几乎就是为二分查找（Binary Search）量身定做的场景。

二分查找的搜索空间：

• 下界（low）：max(weights)。因为任何一趟运输，至少要能装下最重的那个货物。
• 上界（high）：sum(weights)。最极端的情况，用一辆车一趟拉完所有货物（如果k>=1且允许的话，但我们的算法验证过程会考虑趟数限制）。 实际上，high可以更紧一些，比如sum(weights)，因为这是理论上的最大值。

我们在这个区间[low, high]内进行二分查找。对于每一个猜测的mid（即假设的limit），我们需要一个验证函数canShip(weights, k, mid)来判断：当货车容量为mid时，能否用不超过2k趟运完所有货物。

那么，验证函数内部用什么算法？既然我们要判断“能否用不超过2k个容量为mid的箱子装下所有货物”，这就是一个贪心算法的典型应用场景——尽可能让每一趟装得多。

验证函数的贪心策略（以“趟”为单位）：

1. 初始化当前趟的剩余容量current_load = mid，已使用趟数trips = 0。
2. 遍历已排序的货物重量列表（通常从大到小遍历效率更高，容易先装大件）。
3. 对于每个货物weight：
   • 如果current_load >= weight，说明当前趟还能装下，就装进去，current_load -= weight。
   • 如果current_load < weight，说明当前趟装不下这个货物了。那么开启新的一趟（trips += 1，current_load = mid - weight）。
4. 遍历结束后，别忘了最后一趟也需要计数，所以总趟数为trips + 1。
5. 判断总趟数trips + 1 <= 2 * k是否成立。成立则说明mid这个容量可行；否则不可行。

为什么贪心是有效的？对于判定性问题“是否存在一种装法”，在给定容量下，尽可能填满每一趟（贪心）是一种高效的验证方法。如果贪心装法都需要的趟数超过了2k，那么其他任何装法需要的趟数只会更多（或相等），所以mid这个容量肯定不行。反之，如果贪心装法成功了，则mid这个容量可行。这保证了二分查找的正确性。

算法整体框架：

1. 计算low = max(weights),high = sum(weights)。
2. while (low < high):
   • mid = low + (high - low) / 2(防止整数溢出)。
   • 调用canShip(weights, k, mid)进行验证。
   • 如果验证通过 (true)，说明mid可能偏大，尝试寻找更小的，令high = mid。
   • 如果验证不通过 (false)，说明mid太小，需要增大，令low = mid + 1。
3. 循环结束时，low(或high) 即为所求的最小limit。

这个“二分答案+贪心验证”的框架，时间复杂度为O(n log S)，其中n是货物数量，S是货物总重量。这比暴力枚举limit的 O(n * S) 或枚举所有划分方案的指数级复杂度要高效得多。

3. 多语言代码实现与细节剖析

理解了算法框架，我们来看代码实现。不同语言在语法、容器使用上有差异，但核心逻辑一致。我会重点提及其中的关键点和易错点。

3.1 Java实现：面向对象与清晰逻辑

Java版本代码结构清晰，适合体现算法逻辑。

import java.util.Arrays; public class MinShipCapacity { // 贪心验证函数 private boolean canShip(int[] weights, int k, int capacity) { int trips = 0; // 已使用的趟数（注意初始化） int currentLoad = 0; // 当前趟的已装载重量 for (int weight : weights) { // 如果当前趟装不下这个货物 if (currentLoad + weight > capacity) { trips++; // 开启新的一趟 currentLoad = weight; // 新一趟装上当前货物 // 如果趟数已经超过上限，提前返回false if (trips >= 2 * k) { return false; } } else { // 当前趟还能装下 currentLoad += weight; } } // 最后还有一趟未计数（因为 trips 计数的是“开启的新趟”） // 所以总趟数是 trips + 1 return (trips + 1) <= 2 * k; } public int minLimit(int[] weights, int k) { if (weights == null || weights.length == 0 || k <= 0) { return 0; // 根据实际情况处理边界 } // 计算二分查找的边界 int low = Arrays.stream(weights).max().getAsInt(); int high = Arrays.stream(weights).sum(); // 二分查找 while (low < high) { int mid = low + (high - low) / 2; // 防止溢出 if (canShip(weights, k, mid)) { high = mid; // mid可行，尝试更小的 } else { low = mid + 1; // mid不可行，必须增大 } } return low; // 此时 low == high，即为答案 } // 测试用例 public static void main(String[] args) { MinShipCapacity solver = new MinShipCapacity(); int[] weights1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int k1 = 5; System.out.println("测试1 结果: " + solver.minLimit(weights1, k1)); // 应输出 10 int[] weights2 = {3, 2, 2, 4, 1, 4}; int k2 = 3; System.out.println("测试2 结果: " + solver.minLimit(weights2, k2)); // 应输出 6 } }

Java实现关键点解析：

1. canShip函数的趟数计数逻辑：这是最容易出错的地方。代码中trips变量记录的是“已经开启的新趟数”。当发现当前趟装不下新货物时，我们trips++，然后新的一趟从当前货物开始装(currentLoad = weight)。遍历结束后，最后一趟（即装着最后一批货物的那一趟）并没有触发“开启新趟”，所以总趟数需要trips + 1。这种计数方式逻辑清晰，不易出错。
2. 提前剪枝：在canShip循环中，一旦trips >= 2 * k，就可以立即返回false，无需继续遍历后面的货物。这是一个重要的优化。
3. 二分查找的细节：使用mid = low + (high - low) / 2计算中点，是防止(low + high)可能出现的整数溢出标准写法。循环条件while (low < high)和更新规则 (high = mid,low = mid + 1) 构成了寻找左边界（第一个满足条件的值）的标准二分模式。
4. 使用Stream API计算边界：Arrays.stream(weights).max().getAsInt()和.sum()让代码更简洁，但要注意空数组情况。

3.2 C语言实现：追求效率与底层控制

C语言版本更注重效率和内存控制，适合理解算法最本质的操作。

#include <stdio.h> #include <stdlib.h> #include <limits.h> // 比较函数，用于qsort降序排序（从大到小） int compare(const void* a, const void* b) { return (*(int*)b) - (*(int*)a); } // 贪心验证函数 int canShip(int* weights, int weightsSize, int k, int capacity) { int trips = 0; // 已使用的趟数（已开启的新趟） int currentLoad = 0; // 为了贪心效果更好，可以先对重量进行降序排序（装大件优先） // 注意：这里假设传入的weights副本或原数组可被排序。为了不影响原数组，通常需要拷贝。 // 本例中为了清晰，假设weights已降序排序。 for (int i = 0; i < weightsSize; ++i) { if (currentLoad + weights[i] > capacity) { trips++; currentLoad = weights[i]; if (trips >= 2 * k) { return 0; // false } } else { currentLoad += weights[i]; } } // 最后一趟 return (trips + 1) <= 2 * k; } // 计算数组最大值 int maxInArray(int* arr, int size) { int maxVal = INT_MIN; for (int i = 0; i < size; ++i) { if (arr[i] > maxVal) maxVal = arr[i]; } return maxVal; } // 计算数组和 int sumOfArray(int* arr, int size) { int total = 0; for (int i = 0; i < size; ++i) { total += arr[i]; } return total; } int minLimit(int* weights, int weightsSize, int k) { if (weightsSize == 0 || k <= 0) return 0; // 为了贪心，先对重量降序排序（创建副本以避免修改输入） int* sortedWeights = (int*)malloc(weightsSize * sizeof(int)); if (!sortedWeights) return -1; // 内存分配失败 for (int i = 0; i < weightsSize; ++i) { sortedWeights[i] = weights[i]; } qsort(sortedWeights, weightsSize, sizeof(int), compare); int low = maxInArray(sortedWeights, weightsSize); // 或 sortedWeights[0]，因为已降序 int high = sumOfArray(sortedWeights, weightsSize); int ans = high; // 初始化答案为上界 while (low <= high) { // 另一种二分写法：<= int mid = low + (high - low) / 2; if (canShip(sortedWeights, weightsSize, k, mid)) { ans = mid; // 记录可行解 high = mid - 1; // 尝试寻找更小的解 } else { low = mid + 1; } } free(sortedWeights); // 释放副本内存 return ans; } int main() { int weights1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int k1 = 5; int size1 = sizeof(weights1) / sizeof(weights1[0]); printf("测试1 结果: %d\n", minLimit(weights1, size1, k1)); // 应输出 10 int weights2[] = {3, 2, 2, 4, 1, 4}; int k2 = 3; int size2 = sizeof(weights2) / sizeof(weights2[0]); printf("测试2 结果: %d\n", minLimit(weights2, size2, k2)); // 应输出 6 return 0; }

C语言实现关键点解析：

1. 排序与副本：贪心验证时，从大到小处理货物通常能得到更优的趟数（更容易先填满容量）。C语言中需要手动管理内存，因此创建了原数组的副本sortedWeights并进行降序排序 (qsort配合自定义的compare函数)。务必记得最后释放malloc分配的内存，否则会造成内存泄漏。
2. 二分查找的另一种写法：这里使用了while (low <= high)的循环条件，并在找到可行解时用ans记录。这种写法更直观地体现了“搜索”过程，最终ans即为答案。两种二分写法（while (low < high)和while (low <= high)）都是正确的，选择一种并理解其边界条件即可。
3. 手动计算最大值和总和：C标准库没有直接求数组最大值和和的函数，需要手动遍历计算。INT_MIN来自limits.h，用于初始化最大值变量。
4. 函数返回值：canShip返回int类型表示布尔值（0为假，非0为真），这是C语言的常见做法。

3.3 C++实现：利用STL的简洁与高效

C++版本结合了面向对象和泛型编程的优势，代码通常更简短。

#include <iostream> #include <vector> #include <algorithm> #include <numeric> // 用于 accumulate using namespace std; class Solution { public: int minLimit(vector<int>& weights, int k) { if (weights.empty() || k <= 0) return 0; // 降序排序有利于贪心 sort(weights.begin(), weights.end(), greater<int>()); int low = weights.front(); // 最大值，因为已降序 int high = accumulate(weights.begin(), weights.end(), 0); int ans = high; while (low <= high) { int mid = low + (high - low) / 2; if (canShip(weights, k, mid)) { ans = mid; high = mid - 1; } else { low = mid + 1; } } return ans; } private: bool canShip(const vector<int>& weights, int k, int capacity) { int trips = 0; int currentLoad = 0; for (int weight : weights) { if (currentLoad + weight > capacity) { if (++trips >= 2 * k) { // 提前剪枝 return false; } currentLoad = weight; } else { currentLoad += weight; } } // 注意趟数计算： trips 是新增趟数，总趟数为 trips + 1 return (trips + 1) <= 2 * k; } }; int main() { Solution sol; vector<int> weights1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int k1 = 5; cout << "测试1 结果: " << sol.minLimit(weights1, k1) << endl; // 10 vector<int> weights2 = {3, 2, 2, 4, 1, 4}; int k2 = 3; cout << "测试2 结果: " << sol.minLimit(weights2, k2) << endl; // 6 return 0; }

C++实现关键点解析：

1. STL算法的使用：sort(weights.begin(), weights.end(), greater<int>())一行代码完成降序排序。accumulate(weights.begin(), weights.end(), 0)一行代码计算总和。这大大简化了代码。
2. 引用传递：canShip函数参数使用const vector<int>&，避免不必要的拷贝，提高效率。
3. 循环与自增操作：在if (++trips >= 2 * k)中，将自增和判断合并在一行，是C/C++中常见的简洁写法。但要注意运算顺序和可读性。
4. 类封装：将解法和验证函数封装在Solution类中，是应对算法题目的常见模式，结构清晰。

3.4 Python实现：简洁直观与快速验证

Python版本以其极简的语法和强大的内置函数，非常适合快速实现和验证算法思路。

from typing import List class Solution: def minLimit(self, weights: List[int], k: int) -> int: if not weights or k <= 0: return 0 # 降序排序有利于贪心 weights.sort(reverse=True) low = weights[0] # 最大值 high = sum(weights) def can_ship(capacity: int) -> bool: """验证给定容量是否可行""" trips = 0 # 已开启的新趟数 current_load = 0 for w in weights: if current_load + w > capacity: trips += 1 current_load = w if trips >= 2 * k: # 提前剪枝 return False else: current_load += w # 最后一趟未触发 trips++，所以总趟数是 trips + 1 return (trips + 1) <= 2 * k # 二分查找 while low < high: mid = (low + high) // 2 if can_ship(mid): high = mid # mid可行，尝试更小的 else: low = mid + 1 # mid不可行，必须增大 return low # 此时 low == high # 测试 if __name__ == "__main__": sol = Solution() print("测试1 结果:", sol.minLimit([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5)) # 10 print("测试2 结果:", sol.minLimit([3, 2, 2, 4, 1, 4], 3)) # 6

Python实现关键点解析：

1. 内置函数与列表推导：sum(weights),weights.sort(reverse=True)使得代码非常简洁。Python的整数不会溢出，所以(low + high) // 2写法没问题。
2. 内部函数：将验证函数can_ship定义为minLimit方法内的内部函数，可以自然地访问外部函数的参数weights和k，无需再次传递，使代码更紧凑。
3. 清晰的二分查找：使用while low < high:和high = mid/low = mid + 1的模式，是寻找最小满足值（左边界）的经典写法，最终low即为答案。
4. 类型提示：from typing import List和-> int,-> bool等类型提示虽然不是运行时强制，但能极大提高代码的可读性和可维护性，尤其是在复杂的项目中。

4. 实战调试与边界情况处理

代码写完了，直接运行测试用例通过就万事大吉了吗？当然不是。机试和实际开发中，边界情况和极端输入才是真正的挑战。下面是我在练习和帮别人调试时总结的几个关键点。

4.1 必须考虑的边界条件

1. 空货物列表或零货车：

   • 如果weights为空数组，无论k是多少，都不需要运输，最小限载可以认为是0。但题目通常保证输入有效，不过防御性编程要考虑。代码中应添加判断，返回一个合理值（如0）。
   • 如果k <= 0，货车数量非正，问题无解。同样需要处理。

2. 单件货物超重：二分查找的下界是max(weights)，这保证了一趟至少能运走最重的货物。这是算法正确性的基础。

3. 货物总重极大或货车数极少：当k很小，而货物总重很大时，计算出的high边界 (sum(weights)) 可能非常大。二分查找的复杂度是O(n log S)，其中S是high。在极端情况下，如果重量和达到10^9甚至更大，log S大约为30，配合n(比如10^5)，整体复杂度O(3 * 10^6)是可以接受的。但要注意，在canShip函数中，如果capacity设置得非常不合理（比如很小），贪心遍历会提前因为趟数超标而退出，实际运行很快。

4. 货物重量全部相等：这是检验贪心策略的好例子。例如weights = [5,5,5,5],k=1。我们需要2k=2趟。最小容量是多少？贪心算法会正确工作：容量至少为10才能两趟运完（每趟两个货物）。二分查找会找到这个值。

4.2 贪心验证中的两个易错陷阱

1. 趟数计数逻辑：这是最高频的错误。务必明确trips变量到底代表什么。

   • 错误理解1：trips初始化为1，表示第一趟。遇到装不下的货物就trips++。最后判断trips <= 2*k。这种写法在货物恰好装满最后一趟时是对的，但如果最后一趟没装满，trips其实多算了一趟？仔细想想边界，容易混乱。
   • 错误理解2：trips初始化为0，表示已完成的趟数。每次开启新趟时trips++。遍历结束后，如果currentLoad > 0，则trips++。最后判断trips <= 2*k。这种写法也可以，但稍显冗余。
   • 推荐理解（本文采用）：trips初始化为0，表示“已经开启的新趟数”。当需要为当前货物开启新的一趟时，trips++，并且这新的一趟立刻装上了当前货物 (currentLoad = weight)。遍历结束后，总有一趟（最后一趟）是没有触发“开启新趟”操作的，所以总趟数 =trips + 1。这个逻辑非常清晰，且便于提前剪枝（判断trips >= 2*k时就失败）。

2. 排序顺序的影响：贪心验证时，遍历货物的顺序会影响单次验证的结果吗？理论上，对于判定性问题“是否存在一种装法”，如果采用“尽可能装”的贪心，从大到小遍历通常更容易触发“装不下”而开启新趟，从而可能得到偏大的所需趟数。但这恰恰是我们需要的——如果连这种“保守”的贪心都能在2k趟内装完，那么其他装法肯定也能。反之，如果这种贪心都装不完，那么这个容量肯定不行。所以，降序排序是一个优化，它使验证函数更“严格”，但不影响二分查找最终结果的正确性。在实际编码中，排序是一个O(n log n)的操作，在二分查找外做一次即可。

4.3 调试与测试用例设计

自己编写几个有代表性的测试用例，是确保代码正确的关键。

# 补充一些有价值的测试用例 def test(): sol = Solution() # 用例1: 常规情况 assert sol.minLimit([1,2,3,4,5,6,7,8,9,10], 5) == 10 # 用例2: 另一组数据 assert sol.minLimit([3,2,2,4,1,4], 3) == 6 # 用例3: 货车数充足，一趟运完 assert sol.minLimit([1,1,1,1], 10) == 1 # 容量只需不小于最大货物重1 # 用例4: 货车数很少，需要多趟 assert sol.minLimit([10,20,30,40], 1) == 50 # 2趟，最优装法 (10+40), (20+30) # 用例5: 单个货物 assert sol.minLimit([100], 1) == 100 # 用例6: 所有货物重量相同 assert sol.minLimit([5,5,5,5], 1) == 10 # 需要2趟，每趟容量10 # 用例7: k很大，但货物很重 assert sol.minLimit([1000], 5) == 1000 # 用例8: 空数组 (边界) assert sol.minLimit([], 5) == 0 print("所有测试用例通过！") if __name__ == "__main__": test()

设计测试用例时，要覆盖：最小输入、最大输入、恰好装满、需要精确调度、边界值（如k=1）、所有元素相等、升序/降序/乱序等情况。

5. 算法扩展与同类问题联想

掌握了“统一限载货物数最小值”这道题，你就掌握了一类问题的通解。这类问题在力扣（LeetCode）上有很多变种，核心都是“在满足某种约束条件下，最小化最大值（或最大化最小值）”，并且验证函数通常可以用贪心或动态规划来实现。

经典同类问题举例：

1. 包裹运输问题（LeetCode 1011, 410）：

   • 1011. 在 D 天内送达包裹的能力：与本题几乎一模一样，只是把“货车”换成了“天数”，把“最多两趟”换成了“D天”。验证函数canShip的逻辑完全一致。
   • 410. 分割数组的最大值：给定一个数组和一个整数k，将数组分成k个连续子数组，使得这k个子数组各自和的最大值最小。这是“最小化最大值”的另一个典型表述，验证函数需要判断“当子数组和上限为mid时，能否将数组分成不超过k段”。这同样可以用贪心验证。

2. 工人分配问题（LeetCode 1231）：

   • 1231. 分享巧克力：你有一系列巧克力块，需要分给k个朋友，你想自己留一块，并且你希望你自己得到的那块甜度总和尽可能大。同时，每个朋友得到的巧克力必须是连续的。这可以转化为：找到一个甜度值X，使得在满足每个朋友得到连续巧克力且甜度和不小于X的前提下，能分出k份。验证函数需要判断“甜度下限为X时，能否分出至少k份连续子数组”。这同样是二分答案+贪心验证。

解决这类问题的通用步骤：

1. 识别问题类型：问题是否在求“最小化最大值”或“最大化最小值”？目标值是否在一个可预测的范围内？
2. 定义验证函数：给定一个猜测值mid，能否设计一个相对高效（通常是 O(n) 或 O(n log n)）的算法，来判断mid是否可行？贪心是首选。
3. 确定二分边界：明确搜索空间的下界low和上界high。low通常是理论最小值（如单件最大重量），high通常是理论最大值（如总重量）。
4. 套用二分框架：使用标准的二分查找模板，根据验证结果收缩搜索区间，直到找到边界值。

最后，关于代码本身，在机试中除了正确性，代码的整洁度和可读性也很重要。清晰的变量命名、适当的注释、统一的缩进，都能给阅卷人留下好印象。例如，把二分查找和验证函数分开，主函数逻辑简洁，这在时间紧张的机试中其实是节省时间的——结构清晰，自己调试起来也快。