Greedy Algorithm - Taking the Student Management System as an Example

2024-07-12

1.Greedy Algorithmintroduce

1. Algorithm ideas

The basic idea of the greedy algorithm is to proceed step by step from an initial solution to the problem. According to a certain optimization measure, each step must ensure that a local optimal solution can be obtained. Only one data is considered at each step, and its selection should meet the conditions of local optimization. If the next data is no longer a feasible solution when connected with the partial optimal solution, the data will not be added to the partial solution until all data are enumerated or the algorithm stops if no more data can be added.

The greedy algorithm generally proceeds as follows:

① Establishmentmathematical modelTo describe the problem.

② Divide the problem to be solved into several sub-problems.

③Solve each sub-problem and obtain the local optimal solution of the sub-problem.

④Synthesize the local optimal solution of the sub-problem into a solution to the original problem.

Greedy algorithm is a simpler and faster design technique for finding the optimal solution to some problems. The characteristic of greedy algorithm is that it proceeds step by step, often based on the current situation and making the best choice according to a certain optimization measure, without considering various possible overall situations, thus saving a lot of time that must be spent on exhausting all possibilities to find the optimal solution. Greedy algorithm adoptstop down, make successive greedy choices in an iterative way. Each time a greedy choice is made, the problem is simplified into a smaller sub-problem. Through each step of greedy choice, an optimal solution to the problem can be obtained. Although it is necessary to ensure that a local optimal solution can be obtained at each step, the resulting global solution may not always be optimal, so the greedy algorithm does not backtrack [2].

2. Code Introduction


 
    /**
     * 为指定学生推荐最合适的课程。
     * @param scanner 用于接收用户输入的Scanner对象。
     * @param studentService 用于获取学生信息的服务。
     * @param courseService 用于获取课程列表的服务。
     */
    public static void recommendBestCourse(Scanner scanner, StudentService studentService, CourseService courseService) {
        // 提示用户输入学生ID并接收输入
        System.out.print("输入学生ID：");
        int studentID = scanner.nextInt();
        scanner.nextLine(); // 消耗换行符
 
        // 根据学生ID获取学生信息，如果学生不存在则返回
        Student student = studentService.getStudentById(studentID);
        if (student == null) {
            System.out.println("未找到该学生。");
            return;
        }
 
        // 获取所有课程的列表，如果没有课程信息则返回
        List<Course> courses = courseService.listAllCourses();
        if (courses.isEmpty()) {
            System.out.println("当前没有课程信息。");
            return;
        }
 
        // 使用贪心算法推荐最合适的课程
        Course bestCourse = findBestCourse(student, courses);
        if (bestCourse != null) {
            // 如果找到最佳课程，打印课程信息
            System.out.println("推荐的最合适课程是：" + bestCourse.getCourseName());
            System.out.println("课程ID: " + bestCourse.getCourseID());
            System.out.println("学分: " + bestCourse.getCreditHours());
        } else {
            System.out.println("没有找到合适的课程。");
        }
    }
 
    /**
     * 使用贪心算法找到最合适的课程。
     * @param student 需要推荐课程的学生。
     * @param courses 可供选择的所有课程列表。
     * @return 最佳课程对象。
     */
    private static Course findBestCourse(Student student, List<Course> courses) {
        Course bestCourse = null; // 用于存储当前找到的最佳课程
        int maxScore = Integer.MIN_VALUE; // 用于存储当前最高分数
 
        // 遍历所有课程
        for (Course course : courses) {
            // 计算每个课程的得分
            int score = calculateCourseScore(student, course);
            // 如果当前课程的得分高于已知最高分数，则更新最佳课程和最高分数
            if (score > maxScore) {
                maxScore = score;
                bestCourse = course;
            }
        }
 
        // 返回得分最高的课程作为最佳课程推荐
        return bestCourse;
    }
 
    /**
     * 计算单个课程的得分，用于评估课程的适宜性。
     * @param student 学生对象。
     * @param course 课程对象。
     * @return 计算得到的课程得分。
     */
    private static int calculateCourseScore(Student student, Course course) {
        int score = 0; // 初始化得分
 
        // 学分越高，得分越高，这里假设每1学分得10分
        score += course.getCreditHours() * 10;
 
        // 如果学生未修过该课程，额外加分，这里假设额外加50分
        List<Grade> grades = student.getGrades(new GradeService()); // 获取学生已修课程的列表
        boolean isTaken = grades.stream().anyMatch(grade -> grade.getCourseID() == course.getCourseID());
        if (!isTaken) {
            score += 50;
        }
 
        // 返回计算得到的得分
        return score;
    }

3. Use a greedy algorithm to recommend the most suitable course for a specific student

1. Method definition:
- `recommendBestCourse` is a static method that receives a `Scanner` object for user input, and `StudentService` and `CourseService` service layer objects for obtaining student and course information.

2. User input processing:
- The program first prompts the user to enter a student ID and then uses the Scanner object to read the input value.

3. Student Information Acquisition:
- Use the `studentService.getStudentById(studentID)` method to get student information based on the student ID. If the student does not exist, print a prompt message and end the method execution.

4. Get the course list:
- Call `courseService.listAllCourses()` to get a list of all available courses. If there is no course information, print a prompt message and end the method execution.

5. Recommendation logic:
- Use the greedy algorithm to recommend the most suitable course for the student by calling the `findBestCourse` method.

6. Greedy algorithm implementation:
- The `findBestCourse` method iterates over all courses and calculates a score for each course through the `calculateCourseScore` method. The course with the highest score is selected as the best recommendation.

7. Score calculation:
- The `calculateCourseScore` method defines the logic for calculating the course score. In this example, the score is based on two factors: the number of credits for the course and whether the student has taken the course. The higher the number of credits, the higher the score, and if the student has not taken the course, additional points are added.

8. Recommendation result output:
- If the best course is found, print out the course name, course ID and credit information. If there is no suitable course, print out the corresponding prompt information.

Technology Sharing