动态规划算法-以中学排课管理系统为例

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作为价值的代表。