算法(三)——贪心算法

news/2024/12/12 18:28:39/

文章目录

    • 定义
    • 基本原理
    • 基本思路
    • 优缺点
      • 优点
      • 缺点
    • 经典案例及解析
      • 找零问题
        • 问题描述
        • 贪心思路
        • 算法解析
        • java代码示例
      • 活动选择问题
        • 问题描述
        • 贪心思路
        • 算法解析
        • java代码示例
      • 车辆路径问题
        • 问题描述
        • 贪心思路
        • 算法分析
        • java代码示例

定义

贪心算法是指在求解问题时,总是做出在当前来看是最好的选择,不从整体最优上加以考虑,只做出在某种意义上的局部最优解。在一些特定的问题中,贪心算法可以通过逐步构建最优解来实现全局最优。

基本原理

贪心算法的核心在于它所具有的贪心选择性质。这意味着在对问题求解时,每一步都可以做出一个在当前看来是最优的选择,而不用考虑整体的最优解。
例如,在找零问题中,假设我们有无限量的面值为 25 美分、10 美分、5 美分和 1 美分的硬币,要找给顾客 63 美分的零钱。贪心算法的做法是,每次都选择尽可能大面值的硬币,先选 2 个 25 美分,剩下 13 美分,再选 1 个 10 美分,剩下 3 美分,接着选 3 个 1 美分。这种每一步都选择当前最优(面值最大的硬币)的方式就是贪心选择。

基本思路

从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时,算法停止。

但是存在问题:
不能保证求得的最后解是最佳的;
不能用来求最大或最小解问题;
只能求满足某些约束条件的可行解的范围。

优缺点

优点

简单易懂:
贪心算法通常非常直观和易于理解,解决问题的思路简单直接。

局部最优解:
贪心算法通过每一步选择当前最优解(局部最优解),尝试构建全局最优解。

高效:
贪心算法的时间复杂度通常较低,适合解决某些大规模问题。常见的时间复杂度为 O(nlogn) 或 O(n)。

应用广泛:
贪心算法在诸如图论(如最小生成树、最短路径)、任务调度、资源分配等多个领域有广泛的应用。

缺点

局限性:
贪心算法并不总能找到问题的最优解。它依赖于每一步的局部最优选择,可能会错过全局最优解。例如,背包问题的贪心算法不能保证找到最优解。

问题依赖性:
贪心算法只有在某些特定类型的问题(满足贪心选择性质和最优子结构性质)中才能有效工作。对于不满足这些性质的问题,贪心算法无法保证最优解。

分析复杂:
对于某些问题,证明贪心算法的正确性和最优性可能较为复杂,需要仔细的数学推导和验证。

无回溯:
贪心算法一旦做出选择,就不会回溯或改变决定。因此,一旦做出错误的选择,就无法修正。

经典案例及解析

找零问题

问题描述

给定一些面额不同的硬币,如1元、5元、10元,要找零n元,找零的硬币数量要尽可能少。

贪心思路

在每一步选择中,选择面额最大的硬币,直到找零的总金额达到n

算法解析

先初始化一个空列表,用于存储找零的硬币。从面额最大的硬币开始,将尽可能多的这个硬币加入列表,直到总金额超过n。如果总金额等于n,算法结束。否则,将面额减小到次大的硬币,重复上述步骤。

java代码示例
import java.util.ArrayList;
import java.util.List;public class CoinChangeGreedy {public static void main(String[] args) {int n = 28; // 需要找零的金额int[] coins = {10, 5, 1}; // 可用的硬币面额List<Integer> result = getMinimumCoins(n, coins);// 输出结果System.out.println("所需硬币数量: " + result.size());System.out.println("硬币面额: " + result);}public static List<Integer> getMinimumCoins(int n, int[] coins) {List<Integer> result = new ArrayList<>();// 遍历硬币面额,从大到小for (int coin : coins) {// 尽可能多地使用当前面额的硬币while (n >= coin) {result.add(coin);n -= coin;}}return result;}
}

本贪心算法适用于硬币面额满足贪心选择性质的情况。在本例中,10 和 5 的面额对于任何情况都能进行贪心选择,因此算法是有效的。如果硬币面额不同,比如 {1, 3, 4},则贪心策略可能无法获得最优解。

活动选择问题

问题描述

给定一系列活动,每个活动都有开始时间和结束时间,目标是选择尽可能多的互不相交的活动。

贪心思路

在每一步选择中,选择结束时间最早的活动,可以腾出更多时间给其他活动。

算法解析

1.排序:首先根据活动的结束时间对活动进行排序。
2.选择活动:从第一个活动开始,选择结束时间最早的活动,并继续选择所有不与已选活动重叠的活动。

java代码示例
import java.util.*;class Activity {int start;  // 活动的开始时间int end;    // 活动的结束时间Activity(int start, int end) {this.start = start;this.end = end;}
}public class ActivitySelection {// 方法:选择尽可能多的互不相交的活动public static List<Activity> selectActivities(List<Activity> activities) {// 1. 按照结束时间排序activities.sort(Comparator.comparingInt(a -> a.end));List<Activity> selectedActivities = new ArrayList<>();// 2. 选择活动int lastEndTime = -1;  // 上一个被选择的活动的结束时间,初始为负值for (Activity activity : activities) {// 如果当前活动的开始时间大于或等于上一个选择的活动的结束时间if (activity.start >= lastEndTime) {// 选择当前活动selectedActivities.add(activity);lastEndTime = activity.end;  // 更新结束时间}}return selectedActivities;}public static void main(String[] args) {// 创建一些活动对象 (开始时间, 结束时间)List<Activity> activities = new ArrayList<>();activities.add(new Activity(1, 4));activities.add(new Activity(3, 5));activities.add(new Activity(0, 6));activities.add(new Activity(5, 7));activities.add(new Activity(8, 9));activities.add(new Activity(5, 9));// 调用选择活动的方法List<Activity> selectedActivities = selectActivities(activities);// 打印选择的活动System.out.println("选中的活动如下:");for (Activity activity : selectedActivities) {System.out.println("活动开始时间: " + activity.start + ", 活动结束时间: " + activity.end);}}
}

车辆路径问题

问题描述

有一组客户点和一个中心仓库,目标是找到一条路径,使得所有客户都被访问,并且路径总长度最短。

贪心思路

从仓库出发,选择离当前位置最近的客户点,重复此过程直到所有客户都被访问。

算法分析

从仓库出发,选择距离仓库最近的客户。访问该客户,然后选择距离当前客户最近的未被访问的客户。重复这个过程,直到所有客户都被访问完。

java代码示例
import java.util.*;
public class GreedyTSP {// 定义一个二维数组表示客户和仓库的坐标static class Point {int x, y;Point(int x, int y) {this.x = x;this.y = y;}// 计算两点之间的欧几里得距离double distanceTo(Point other) {return Math.sqrt(Math.pow(this.x - other.x, 2) + Math.pow(this.y - other.y, 2));}}public static void main(String[] args) {// 仓库的坐标Point warehouse = new Point(0, 0);// 客户的坐标List<Point> customers = Arrays.asList(new Point(2, 3),new Point(5, 2),new Point(8, 8),new Point(6, 7),new Point(1, 6));// 调用贪心算法获取访问路径List<Point> path = greedyTSP(warehouse, customers);// 输出路径System.out.println("访问顺序:");for (Point p : path) {System.out.println("客户位置: (" + p.x + ", " + p.y + ")");}}// 贪心算法实现public static List<Point> greedyTSP(Point warehouse, List<Point> customers) {List<Point> path = new ArrayList<>();Set<Point> visited = new HashSet<>();Point current = warehouse;// 将仓库添加到路径path.add(current);// 循环直到所有客户都被访问while (visited.size() < customers.size()) {Point nearestCustomer = null;double minDistance = Double.MAX_VALUE;// 寻找最近的未访问客户for (Point customer : customers) {if (!visited.contains(customer)) {double dist = current.distanceTo(customer);if (dist < minDistance) {minDistance = dist;nearestCustomer = customer;}}}// 将找到的最近客户添加到路径,并标记为已访问if (nearestCustomer != null) {path.add(nearestCustomer);visited.add(nearestCustomer);current = nearestCustomer; // 更新当前客户为最近客户}}return path;}
}

以上是我对贪心算法学习过程中的一部分内容进行了总结,我一直秉持着只有先了解学习过这些算法思想和原理之后才能对它的应用掌握得更深入,后续还会继续学习总结一系列算法思想,不定时进行总结。


http://www.ppmy.cn/news/1554207.html

相关文章

Java版-图论-最小生成树-Kruskal算法

实现描述 为了造出一棵最小生成树&#xff0c;我们从最小边权的边开始&#xff0c;按边权从小到大依次加入&#xff0c;如果某次加边产生了环&#xff0c;就扔掉这条边&#xff0c;直到加入了 n-1 条边&#xff0c;即形成了一棵树。 实现代码 首选我们对所有的边&#xff0c…

游戏交易系统设计与实现

文末获取源码和万字论文&#xff0c;制作不易&#xff0c;感谢点赞支持。 题目&#xff1a;游戏交易系统设计与实现 摘 要 在如今社会上&#xff0c;关于信息上面的处理&#xff0c;没有任何一个企业或者个人会忽视&#xff0c;如何让信息急速传递&#xff0c;并且归档储存查询…

小皮面板(PHPSTUDY)配置多个域名或IP

问题描述 小皮面板默认采用nginx的静态部署&#xff0c;按照使用nginx的习惯只需要额外添加一个server即可&#xff0c;但是会发现直接往配置文件里添加新的server是不生效的&#xff0c;小皮的官网论坛几乎已经停止维护&#xff0c;因此资料较少&#xff0c;原本也没有仔细使…

深入探索 JVM:原理、机制与实战

一、JVM 概述 JVM&#xff08;Java Virtual Machine&#xff09;是 Java 程序运行的核心组件&#xff0c;它提供了一个独立于硬件和操作系统的执行环境&#xff0c;使得 Java 程序能够在不同平台上具有跨平台的特性。 JVM 主要由以下几部分组成&#xff1a; 类装载器&#xf…

微信小程序 AI 智能名片 2+1 链动模式商城系统中的社群电商构建与价值挖掘

摘要&#xff1a;本文聚焦于微信小程序 AI 智能名片 21 链动模式商城系统&#xff0c;深入探讨社群电商在其中的构建方式与所蕴含的价值。通过剖析社群概念的内涵与发展历程&#xff0c;揭示其在当今电商领域备受瞩目的原因&#xff0c;并详细阐述如何在特定的商城系统架构下&a…

【已解决】windows下安装Git

文章目录 1. 下载Git2. 安装3. 测试安装是否成功 1. 下载Git https://git-scm.com/downloads/win 进入到官网后如下如图&#xff0c;并选择自己需要的版本&#xff0c;点击即可下载 2. 安装 2.1 下载完成后双击打开&#xff0c;点击Next 2.2 选择安装路径 2.3 选择必要组件…

linux之vim

一、模式转换命令 vim主要有三种模式&#xff1a;命令模式&#xff08;Normal Mode&#xff09;、输入模式&#xff08;Insert Mode&#xff09;和底线命令模式&#xff08;Command-Line Mode&#xff09;。 从命令模式切换到输入模式&#xff1a;i&#xff1a;在当前光标所在…

【kafka】常用基础命令使用案例

以下是 Kafka 常用命令的详细汇总&#xff0c;包含了常见的操作命令以及使用案例&#xff0c;表格形式方便查看 命令功能命令格式使用案例查看 Kafka 版本查看 Kafka 的版本信息bin/kafka-topics.sh --version获取 Kafka 版本信息&#xff1a; bin/kafka-topics.sh --version创…