贪心算法-以高校教材管理系统为例

admin2024-07-10  6

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`:用于自定义排序逻辑,这里用于根据学校的需求进行排序

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!