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`：用于自定義排序邏輯，這里用于根據學校的需求進行排序