货车调度贪心算法实现 - 厦大马来西亚分校作业解析

"这篇资源是关于使用C语言实现贪心算法解决货车调度货物问题的厦大马来西亚分校作业。作业的核心是设计一个贪心算法，通过排序货物优先级和重量，来有效地分配货物到多辆货车中，使得每辆车的载重不超过最大限制，并且尽可能地装载更多的货物。" 在C语言编程环境中，该作业涉及到以下知识点： 1. **结构体（Struct）**：定义了一个名为`Goods`的结构体，包含两个成员变量，`weight`表示货物的重量，`priority`表示货物的优先级。结构体是C语言中组合数据类型的一种方式，可以用来封装不同类型的数据。 2. **自定义排序函数（Custom Sorting Function）**：为了根据优先级和重量对货物进行排序，定义了一个名为`cmp`的比较函数。这个函数遵循C++的`std::sort`函数的规则，返回值决定排序的方向。在这里，当优先级相同时，根据重量降序排列；当优先级不相同时，优先级高的排在前面。 3. **贪心算法（Greedy Algorithm）**：贪心算法是一种解决问题的方法，它在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的。在这个问题中，贪心策略是每次都选择优先级最高的货物，直到货车满载或者没有更高优先级的货物。 4. **队列（Queue）**：虽然代码中没有明确使用队列，但队列的概念在货车调度中是隐含的。每个货车可以看作是一个容器，货物按照优先级和重量进入货车（入队），直至货车满载（出队）。 5. **向量（Vector）**：使用`std::vector`来存储货物和货车的装载情况。`vector<vector<int>> res_of_car;`定义了一个二维向量，用于保存每辆货车装载的货物重量。 6. **算法实现**： - 首先，根据`cmp`函数对所有货物进行排序。 - 然后，创建一个新的空货车（二维向量`res_of_car`的一个新元素），并尝试装载货物。每次尝试将优先级最高的货物加入货车，直到货车超载或者没有更高优先级的货物。 - 当货车无法再装载任何货物时，开始新的货车，继续装载剩余的货物，重复此过程，直到所有货物都被处理。 7. **循环与条件判断**：内部的`while`循环用于装载一辆车，外部的`while`循环用于处理所有的货物。`if`语句检查当前货物是否能安全装载到货车，`else if`和`else`部分分别处理当前货物是最后一个货物和超载的情况。 通过这些知识点的应用，学生可以学习如何用C语言编写贪心算法，解决实际问题，如货车调度，同时理解如何设计和实现有效的数据结构和排序策略。