1.動態規劃算法介紹?

1.算法思路

動態規劃算法通常用于求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應于一個值，我們希望找到具有最優值的解。動態規劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動態規劃求解的問題，經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數目太多，有些子問題被重復計算了很多次。如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復計算，節省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計算過，就將其結果填入表中。這就是動態規劃法的基本思路。具體的動態規劃算法多種多樣，但它們具有相同的填表格式。

2.代碼介紹

/private static boolean foundOptimal = false; // 用于全局控制是否找到// 優化課程安排，使用遞歸模擬動態規劃過程private static void optimizeCourseScheduling(Scanner scanner, CourseService courseService) {System.out.print("輸入可用教室數量：");int capacity = scanner.nextInt(); // 用戶輸入教室的容量scanner.nextLine();List<CourseEntity> courses = courseService.getAllCourses(); // 獲取所有課程int n = courses.size(); // 課程總數int[] weights = new int[n]; // 每個課程占用的教室數量int[] values = new int[n]; // 每個課程的價值，這里使用教師ID// 為每門課程分配教師ID和教室資源System.out.println("正在為每門課程分配教師ID和教室資源...");for (int i = 0; i < n; i++) {weights[i] = 1; // 假設每個課程占用一個教室values[i] = courses.get(i).getTeacherId(); // 教師ID作為課程的價值}int maxValue = knapsack(0, weights, values, capacity, n);System.out.println("在可用教室數量為 " + capacity + " 的情況下，最大化的課程安排價值為：" + maxValue);// 初始化標記數組，所有課程初始為未選擇boolean[] selected = new boolean[n];foundOptimal = false; // 重置全局變量printSelectedCourses(0, weights, values, capacity, n, selected, maxValue);if (!foundOptimal) {System.out.println("未找到符合條件的課程安排。");}}// 遞歸函數模擬動態規劃解決背包問題
// 遞歸的深度為課程數量n，每層遞歸的復雜度與教室容量有關private static int knapsack(int index, int[] weights, int[] values, int capacity, int n) {// 基本情況：沒有課程可選或背包容量為0if (index == n || capacity == 0) {return 0;}// 如果當前課程的重量大于背包容量，則不能選擇該課程if (weights[index] > capacity) {return knapsack(index + 1, weights, values, capacity, n);}// 遞歸選擇：選擇包含當前課程或不包含當前課程的最大價值return Math.max(knapsack(index + 1, weights, values, capacity, n), // 不選擇當前課程values[index] + knapsack(index + 1, weights, values, capacity - weights[index], n) // 選擇當前課程);}// 遞歸回溯函數，意圖是打印出被選中的課程和教師IDprivate static boolean printSelectedCourses(int index, int[] weights, int[] values, int currentCapacity, int n, boolean[] selected, int maxValue) {if (foundOptimal) {return true; // 如果已經找到最優解，直接返回}if (index == n) {int currentValue = 0;for (int i = 0; i < n; i++) {if (selected[i]) {currentValue += values[i];}}if (currentCapacity == 0 && currentValue == maxValue) {// 打印當前選擇的課程for (int i = 0; i < n; i++) {if (selected[i]) {System.out.println("選擇的課程教師ID: " + values[i]);}}foundOptimal = true; // 標記已找到最優解return true;}return false;}// 不選擇當前課程selected[index] = false;printSelectedCourses(index + 1, weights, values, currentCapacity, n, selected, maxValue);// 嘗試選擇當前課程if (currentCapacity >= weights[index]) {selected[index] = true;printSelectedCourses(index + 1, weights, values, currentCapacity - weights[index], n, selected, maxValue);}return false;}

3.使用動態規劃算法模擬課程安排優化

1. `optimizeCourseScheduling` 方法：

?? ?作用：優化課程安排，使用遞歸模擬動態規劃過程。

?? ?參數列表：

???? ?`Scanner scanner`：用于接收用戶輸入的掃描器。

???? ?`CourseService courseService`：用于獲取課程數據的服務類。

2. `knapsack` 方法：

?? ?作用：模擬動態規劃解決背包問題，計算最大化的課程安排價值。

?? ?參數列表：

???? ?`int index`：當前處理的課程索引。

???? ?`int[] weights`：每個課程占用的教室數量。

???? ?`int[] values`：每個課程的價值（教師ID）。

???? ?`int capacity`：當前剩余的教室容量。

???? ?`int n`：課程總數。

3. `printSelectedCourses` 方法：

?? ?作用：遞歸回溯函數，意圖是打印出被選中的課程和教師ID。

?? ?參數列表：

???? ?`int index`：當前處理的課程索引。

???? ?`int[] weights`：每個課程占用的教室數量。

???? ?`int[] values`：每個課程的價值（教師ID）。

???? ?`int currentCapacity`：當前剩余的教室容量。

???? ?`int n`：課程總數。

???? ?`boolean[] selected`：標記數組，表示每個課程是否被選擇。

???? ?`int maxValue`：最大化的課程安排價值。

?詳細描述

1. `optimizeCourseScheduling` 方法：

?? ?該方法首先接收用戶輸入的教室容量，然后獲取所有課程數據。

?? ?為每門課程分配教師ID和教室資源，并初始化權重和價值數組。

?? ?調用 `knapsack` 方法計算最大化的課程安排價值。

?? ?初始化標記數組 `selected`，并調用 `printSelectedCourses` 方法打印出被選中的課程和教師ID。

?? ?如果未找到符合條件的課程安排，則輸出提示信息。

2. `knapsack` 方法：

?? ?該方法是用于模擬動態規劃解決背包問題。

?? ?基本情況：如果沒有課程可選或背包容量為0，則返回0。

?? ?如果當前課程的重量大于背包容量，則不能選擇該課程。

?? ?遞歸選擇：選擇包含當前課程或不包含當前課程的最大價值。

3. `printSelectedCourses` 方法：

?? ?該方法是遞歸回溯函數，用于打印出被選中的課程和教師ID。

?? ?如果已經找到最優解，直接返回。

?? ?遞歸終止條件：如果處理完所有課程，計算當前選擇的課程價值，如果滿足條件則打印選擇的課程并標記已找到最優解。

?? ?不選擇當前課程，繼續遞歸處理下一個課程。

?? ?嘗試選擇當前課程，如果當前容量足夠，繼續遞歸處理下一個課程。

總結

這段代碼的核心是一個簡化的課程安排優化問題，模擬動態規劃算法，以解決類似于背包問題的資源分配問題。程序的目標是在有限的教室資源下最大化課程的總價值，這里使用教師ID作為價值的代表。