1.贪心算法介绍
1.算法思路
贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一 步都要确保能获得局部最优解。每一步只考虑一 个数据，其选取应该满足局部优化的条件。若下 一个数据和部分最优解连在一起不再是可行解时， 就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。
贪心算法一般按如下步骤进行：
①建立数学模型来描述问题 。
②把求解的问题分成若干个子问题 。
③对每个子问题求解，得到子问题的局部最优解 。
④把子问题的解局部最优解合成原来解问题的一个解 。
贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯 。
2.代码介绍
// 定义一个方法来计算最优的教材分配方案
private static void calculateOptimalTextbookAllocation(Scanner scanner, SchoolService schoolService, TextbookService textbookService) {
// 获取所有学校的列表和所有教材的列表
List<School> schools = schoolService.listAllSchools();
List<Textbook> textbooks = textbookService.listAllTextbooks();
// 创建一个映射，存储每个学校的需求
Map<Integer, Integer> schoolDemand = new HashMap<>();
for (School school : schools) {
System.out.print("请输入学校ID " + school.getSchoolId() + " 的需求：");
int demand = scanner.nextInt(); // 从用户那里获取需求
schoolDemand.put(school.getSchoolId(), demand); // 存储需求到映射
}
// 创建一个映射，存储每种教材的数量
Map<Integer, Integer> textbookQuantity = new HashMap<>();
for (Textbook textbook : textbooks) {
System.out.print("请输入教材ID " + textbook.getTextbookId() + " 的数量：");
int quantity = scanner.nextInt(); // 从用户那里获取教材数量
textbookQuantity.put(textbook.getTextbookId(), quantity); // 存储教材数量到映射
}
// 使用Java 8的Streams API对学校列表按照需求进行降序排序
// 这里使用了方法引用School::getSchoolId代替lambda表达式
schools.sort(Comparator.comparingInt(School::getSchoolId).reversed());
// 创建一个映射，存储最终的教材分配结果
Map<Integer, Integer> allocation = new HashMap<>();
for (School school : schools) {
int demand = schoolDemand.get(school.getSchoolId()); // 获取当前学校的需求
for (Textbook textbook : textbooks) {
int quantity = textbookQuantity.get(textbook.getTextbookId()); // 获取当前教材的数量
// 如果教材数量和需求都大于0，则进行分配
if (quantity > 0 && demand > 0) {
int allocated = Math.min(demand, quantity); // 计算可以分配的数量
// 更新分配结果映射，增加分配数量
allocation.put(school.getSchoolId(), allocation.getOrDefault(school.getSchoolId(), 0) + allocated);
// 从教材数量中减去已分配的数量
textbookQuantity.put(textbook.getTextbookId(), quantity - allocated);
// 减少学校的需求
demand -= allocated;
}
}
}
// 打印最优教材分配方案
System.out.println("最优教材分配方案：");
for (School school : schools) {
int allocated = allocation.getOrDefault(school.getSchoolId(), 0); // 获取学校分配到的教材数量
System.out.println("学校ID：" + school.getSchoolId() + "，分配数量：" + allocated);
}
}3.应用概括
使用的算法是一个简单的贪心算法，尝试为每个学校分配尽可能多的教材，直到满足学校的需求或教材用尽。学校根据需求从大到小排序，以确保需求量大的学校能够优先获得教材分配。教材分配过程是一个迭代过程，每次迭代中都会尝试为当前学校分配尽可能多的教材，直到需求被满足或教材用尽。这个过程一直持续，直到所有学校都得到了尽可能多的教材分配。
算法流程：
1. 初始化阶段：通过服务接口获取所有学校和教材的列表，初始化存储学校需求和教材数量的数据结构。
2. 数据收集：通过控制台输入，收集每个学校的需求和每种教材的可用数量。
3. 排序操作：将学校列表按照需求从大到小排序，以便优先满足需求量较大的学校。
4. 分配过程：遍历排序后学校的列表，对每所学校尝试分配教材，直到学校需求得到满足或教材用尽。
5. 更新状态：在分配过程中，更新已分配教材的数量和学校剩余需求。
6. 输出结果：打印最终的教材分配方案。
代码实现：
使用 `Scanner` 从控制台读取用户输入，获取学校的需求和教材的数量。
使用 `HashMap` 存储学校需求和教材数量，便于快速访问和更新。
使用 `List` 存储学校对象，并利用 `Collections.sort()` 方法进行排序。
通过两层嵌套循环实现分配逻辑：外层循环遍历学校，内层循环遍历教材。
数据结构：
`List<School>` 和 `List<Textbook>`：存储学校和教材对象的列表，便于进行排序和遍历。
`Map<Integer, Integer>`：存储学校需求和教材数量，键为学校ID或教材ID，值为需求或数量。这种映射提供了快速查找和更新的能力。
`Comparator.comparingInt`：用于自定义排序逻辑，这里用于根据学校的需求进行排序
