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) {
// 基本情况：没有课程可选或背包容量为0
if (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) // 选择当前课程
);
}
// 递归回溯函数，意图是打印出被选中的课程和教师ID
private 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作为价值的代表。
