贪心算法---java---黑马

贪心算法

1)Greedy algorithm

称之为贪心算法或者贪婪算法，核心思想是

  1. 将寻找最优解的问题分为若干个步骤
  2. 每一步骤都采用贪心原则，选取当前最优解
  3. 因为未考虑所有可能，局部最优的堆叠不一定得到最终解最优

贪心算法例子

Dijkstra

while (!list.isEmpty()) {
    // 选取当前【距离最小】的顶点
    Vretex curr = chooseMinDistVertex(list);
    
    // 更新当前顶点到相邻顶点距离
    updateNeighboursDish(curr);
    
    // list集合中移除当前顶点
    list.remove(curr);
    // 标记当前顶点已被访问
    curr.visited = true;
}
  • 未能找到最短路径：存在负边 情况，得不到正确解；
  • 贪心原则会认为本次已找到该顶点的最短路径，使得该顶点赋为已访问 ；
  • 与之对比，Bellman-Ford算法并未考虑局部距离最小顶点，而是每次处理所有边 ，不会出错，当然效率不如Dijkstra算法；

prim

while (!list.isEmpty()) {
    // 选取当前【距离最小】的顶点
    Vretex curr = chooseMinDistVertex(list);
    // 更新当前顶点到相邻顶点距离
    updateNeighboursDish(curr);
    // list集合中移除当前顶点
    list.remove(curr);
    // 标记当前顶点已被访问
    curr.visited = true;
}

prim与Dijkstra的区别在于，根据距离选取最小顶点不同，Dijkstra算法是一个累加距离，而prim算法中距离是跟相邻顶点间的距离 。

KrusKal

List<String> list = new ArrayList<>();
DisjoinSet set = new DisjoinSet(size);
while (list.size() < size - 1) {
    // 选取当前【距离最短】的边
    Edge poll = queue.poll();
    int i = set.find(poll.start);
    int j = set.find(poll.end);
    // 判断两个集合是否相交
    if (i != j) {// 未相交
        list.add(poll);
        set.union(i, j);	// 相交操作
    }
    
}

其他贪心算法例子

  • 选择排序、堆排序
  • 拓扑排序
  • 并查集和中的union by size 和union by height
  • 哈夫曼编码
  • 钱币找零
  • 任务编排
  • 近似算法

零钱兑换ⅡLeetcode518

递归实现

public class Leetcode518 {
    public int change(int[] coins, int amount) {
        return coinChange(coins, 0, amount, new LinkedList<>(), true);
    }
    
    public int coinChange(int[] coins, int index, int amount, LinkedList<Integer> stack, boolean first) {
        if (!first) {
            stack.push(coins[i]);
        }
        int sum = 0;
        if (amount == 0) {
            System.out.printlin(stack);
            sum = 1;
        } else if (amount < 0) {
            System.out.println(stack)
            sum = 0;
        } else {
            for(int i = index; i < coins.length; i++) {
               sum += coinChange(coins, i, amount - coins[i], stack, false);
            }
        }
        if (!stack.isEmpty()) {
            stack.pop();
        }
        return sum;
    }
}

零钱兑换Leetcode322

递归实现

public class Leetcode322 {
    
    static int min = -1;
    
    public int change(int[] coins, int amount) {
        coinChange(coins, 0, amount, new AtomicInteger(-1), new LinkedList<Integer>(), true);
        return min;
    }
    
    public void coinChange(int[] coins, int index, int amount, AtomicInteger count, LinkedList<Integer> stack, boolean first) {
        if (!first) {
            stack.push(coins[i]);
        }
        count.incrementAndGet();	// count++;
        int sum = 0;
        if (amount == 0) {
            System.out.println(stack);
            if (min == -1) {
                min = min.get();
            } else {
                min = Math.min(min, count.get());
            }
        } else {
            for(int i = index; i < coins.length; i++) {
               sum += coinChange(coins, i, amount - coins[i], count, stack, false);
            }
        }
        count.decrementAndGet();	// count--;	
        if (!stack.isEmpty()) {
            stack.pop();
        }
        return sum;
    }
    
    public static void main(String[] args) {
        int[] coins = {5, 2, 1};
        Leetcode322 leetcode = new Leetcode322();
        System.out.printlin(leetcode.coinChange(coins, 5));
    }
}

贪心实现

public class Leetcode322{
    
    public int coinChange(int[] coins, int amount) {
        
        // 前提是coins是降序排序
    	int reminder = amount;
        int count;
        for(int coin : coins) {
            while (reminder > coin) {
                reminder -= coin;
                count++;
            }
            if (reminder == coin) {
                reminder -= coin;
                count++;
                break;
            }
        }
        if (reminder > 0) {
            return -1;
        } else {
            return count;
        }
    }
    
}

但是这个代码放到Leetcode上跑，有些测试用例是不能通过。

动态规划实现

使用动态规划求解，如下面代码

public class Leetcode322{
    
    public int coinChange(int[] coins, int amount) {
        
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for(int coin : coins) {
            for(int j = coin; j < amount + 1; j++) {
                dp[j] = Math.min(dp[j], dp[j - coin] + 1);
            }
        }
        int r = dp[amount];
        return r > amount ? -1 : r;
    }
    
}

哈夫曼编码

Huffman树构建过程

  1. 统计出现频次字符，放入优先级队列
  2. 每次出对两个频次最低元素(小顶堆)，
  3. 当队列中只有一个元素时，构建Huffman树完成
public class Huffman{
    
    static class Node{
        Character ch;
        int freq;
        Node left;
        Node right;
        String code;
        
        public Node(Character ch) {
            this.ch = ch;
        }
        
        public Node(int freq, Node left, Node right) {
            this.freq = freq;
            this.left = left;
            this.right = right;
        }
        
        int getFreq() {
            return freq;
        }
        
        boolean isLeaf() {
            return node.left == null;
        }
        
        @Override
        public void toString() {
            return "Node{" +
                "ch=" + ch + 
                ", freq=" + freq +
                "}";
        }
    }
    
    String str;
    Node root;
    HashMap<Character, Node> map = new HashMap<>();
    public Huffman(String str) {
        this.str = str;
        char[] chars = str.toCharArray();
		
        // 1.统计频次
        for(char ch : chars) {
            if (!map.containsKey(ch)) {
                map.put(ch, new Node(ch));
            } else {
                Node node = map.get(ch);
                node.freq++;
            }
            
            //方法引用
            // Node node = map.computeIfAbsent(ch, Node :: new);
            // node.frea++;
        }
        for(Node node : map.values()) {
            System.out.println(node.toString());
        }
        
        2.构造树
        PriorityQueue<Node> queue = new PriorityQueue<>(
        Comparator.ComparingInt(Node::getFreq)
        );
        queue.offerAll(map.values());
        while (queue.size() >= 2) {
            Node x = queue.poll();
            Node y = queue.poll();
            int f = x.freq + y.freq;
            queue.offer(new Node(f, x, y));
        }
        root = queue.poll();
        System.out.println(root);
        
        // 功能3 计算每个字符编码		//功能4 字符串编码后占几个bit
        int sum = dfs(root, new StringBuilder());		// 得到字符串编码后占的bit
        for(Node node : map.values()) {
            System.out.printlin(node);
        }
        System.out.println(sum);
        
    }
    
    public int dfs(Node node, StringBuilder sb) {
        int sum = 0;
        if (node.isLeaf()) {
            //编码
            node.node = sb.toString();
            sum = sb.length() * node.freq;
         	// System.out.println(sb.toString());   
        } else {
            sum += dfs(node.left, sb.append("0"));
            sum += dfs(node.right, sb.append("1"));
        }
        if (sb.length() > 0) {
            sb.deleteCharAt(sb.length() - 1);
        }
        return sum;
    }
    
    public String encode() {
        char[] chars = str.toCharArray();
        StringBuilder sb = new StringBuilder();
        for(char ch : chars) {
            sb.append(map.get(ch).code);
        }
        return sb.toString();
    }
    
    public String decode(String str) {
        int i = 0;
        char[] chars = str.toCharArray();
        StringBuilder sb = new StringBuilder();
        Node node = root;
        while (i < chars.length) {
            if (!node.isLeaf()) {
                if (chars[i] == '0') {
                    node = node.left;
                } else if (chars[i] == '1'){
                    node = node.right;
                }
                i++;
            } 
            if (node.isLeaf()) {
                sb.append(node.ch);
                node = root;
            }
            
        }
        return sb.toString();
    }
}

活动选择问题

要在一个会议室举办n个活动

  • 每个活动有它们各自的起始和结束时间
  • 找出时间上不冲突的活动组合，能够最充分利用会议室(举办的活动次数最多)
public class ActivitySelectionProblem{
    
    static class Activity{
        int index;
        int start;
        int end;
        
        public Activity(int index, int start, int end) {
            this.index = index;
            this.start = start;
            this.end = end;
        }
        
        public int getEnd() {
            return end;
        }
        
        @Override
        public void tostring() {
            return "Activity(" + index + ")";
        }
    }
    
    public static void main(String[] args) {
        Activity[] activity = new Activity[]{
            new Activity(0, 1, 3),
            new Activity(1, 2, 4),
            new Activity(2, 3, 5)
        }	
        
        Arrays.sort(activity, Comparator.comparingInt(Activity::getEnd))
        System.out.println(activity);
        
        // 
        select(activity, activity.length);
    }
    
    public void select(Activity[] activity, int n) {
        
        List<int[]> res = new ArrayList<>();
        res.add(activity[0]);
        Activity pre = res;
        for(int i = 1; i < n; i++) {
            Activity curr = activity[i];
            if (curr.start >= pre.end) {
                res.add(curr);
                pre =  curr;
            }
        }
        for(Activity a : res) {
            System.out.println(a);
        }
    }
}

Leetcode435

无重叠区间

public class Leetcode435{
    
    public int eraseOverlapIntervals(int[][] intervals) {
        // 根据数组中的第二个元素先升序排序
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        
        List<int[]> res = new ArrayList<>();
        res.add(intervals[0]);
        int[] pre = res.get(0);
        int count = 0;	// 减少个数
        for(int i = 1; i < intervals.length; i++) {
            int[] curr = intervals[i];
            if (curr[0] < pre[1]) {		// 当前的初始值小于前一个的结束值，有冲突
                count++;
            } else {	// 只要当前的初始值大于等于前一个的结束值，则不冲突
                res.add(curr);
                pre = curr;
            }
        }
        return count;
    }
}

分数背包问题

  1. n个液体物品，有重量和价格属性
  2. 现取走10L物品
  3. 每次可以不拿，全拿，拿一部分，问最高价值是多少
    在这里插入图片描述
public class FractionalKnapsackProblem{
    
    static class Item{
        int index;
        int weight;
        int value;
        
        public Item(int index, int weight, int value) {
            this.index = index;
            this.weight = weight;
            this.value = value;
        }
        
        public int perValue() {
            return value / weight;
        }
        
        @Override
        public void toString() {
            return "Item(" + index + ")";
        }
    }
    
    public static void main(String[] args) {
        Item[] items = new Item[]{
            new Item(0, 4, 24),
            new Item(1, 8, 160),
            new Item(2, 2, 4000),
            new Item(3, 6, 108),
            new Item(4, 1, 4000),
        }
        
        select(items, 10);
    }
    
    public int select(Item[] items, int n) {
        Arrays.sort(items, Comparator.comparingInt(Item::preValue).reverse());
        int sum = 0;
        for(int i = 0; i < items.length; i++) {
            Item curr = items[i];
            if (n >= curr.weight) {
                n -= curr.weight;
                sum += curr.value;
            } else {
                sum += curr.perValue() * n;
                break;
            }
        }
        return sum;
    }
}

0-1背包问题

在这里插入图片描述

  1. n个物体都是固体，有重量和价值
  2. 现取走不超过10克物品
  3. 每次可以不拿或者全拿，问最高价值是多少
public class FractionalKnapsackProblem{
    
    static class Item{
        int index;
        int weight;
        int value;
        
        public Item(int index, int weight, int value) {
            this.index = index;
            this.weight = weight;
            this.value = value;
        }
        
        public int perValue() {
            return value / weight;
        }
        
        @Override
        public void toString() {
            return "Item(" + index + ")";
        }
    }
    
    public static void main(String[] args) {
        Item[] items = new Item[]{
            new Item(0, 1, 1000000),
            new Item(1, 4, 1600),
            new Item(2, 8, 2400),
            new Item(3, 5, 30),
        }
        
        select(items, 10);
    }
    
    public int select(Item[] items, int n) {
        Arrays.sort(items, Comparator.comparingInt(Item::preValue).reverse());
        int sum = 0;
        for(int i = 0; i < items.length; i++) {
            Item curr = items[i];
            if (n >= curr.weight) {
                n -= curr.weight;
                sum += curr.value;
            }
        }
        return sum;
    }
}

得到的结果，最大价值结果是：1001630 ，实际上选择钻石和红宝石 得到的价值结果 1002400

贪心算法局限性

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/908545.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

基于vue框架的的留守儿童帮扶管理系统c2691（程序+源码+数据库+调试部署+开发环境）系统界面在最后面。

基于vue框架的的留守儿童帮扶管理系统c2691（程序+源码+数据库+调试部署+开发环境）系统界面在最后面。

系统程序文件列表 项目功能&#xff1a;留守儿童,帮扶活动,申请记录,帮扶机构,帮扶进度,帮扶人,申请加入记录,参与帮扶记录,地区信息 开题报告内容 基于Vue框架的留守儿童帮扶管理系统开题报告 一、研究背景与意义 在现代化进程中&#xff0c;随着城乡经济差异的不断扩大&a…
阅读更多...
MySQL数据库迁移到DM8数据库

MySQL数据库迁移到DM8数据库

1. 达梦新建zsaqks库 2. 打开DM数据迁移工具 3. 新建工程 4. 迁移 - 右击 - 新建迁移 下一步 5. 选择迁移方式 6. MySQL数据源 请输入MySQL数据库信息 7. DM数据库目的 请输入达梦数据库信息 8. 迁移选项 保持对象名大小写(勾选) 9. 指定模式 指定是从数据源复制对象。 10.…
阅读更多...
关于电脑蓝屏的那些解决方案--总有一款适合你

关于电脑蓝屏的那些解决方案--总有一款适合你

目录 背景内存检测硬盘检测拆机除尘上硅脂查看蓝屏日志--计算机管理1796事件进入bios启用安全启动状态创建转储期间出错失败蓝屏crystaldiskinfo查找BitLocker 恢复密钥关闭cpu-c步骤一&#xff1a;进入BIOS设置步骤二&#xff1a;找到CPU C-state设置步骤三&#xff1a;关闭CP…
阅读更多...
HTML 语法规范——代码注释、缩进与格式、标签与属性、字符编码等

HTML 语法规范——代码注释、缩进与格式、标签与属性、字符编码等

文章目录 一、代码注释1.1 使用注释的主要目的1.2 使用建议二、标签的使用2.1 开始标签和结束标签2.2 自闭合标签2.3 标签的嵌套2.4 标签的有效性三、属性四、缩进与格式4.1 一致的缩进4.2 元素单独占用一行4.3 嵌套元素的缩进4.4 避免冗长的行五、字符编码六、小结在开发 HTML…
阅读更多...
项目一：使用 Spring + SpringMVC + Mybatis + lombok 实现网络五子棋

项目一：使用 Spring + SpringMVC + Mybatis + lombok 实现网络五子棋

一&#xff1a;系统展示: 二&#xff1a;约定前后端接口 2.1 登陆 登陆请求&#xff1a; GET /login HTTP/1.1 Content-Type: application/x-www-form-urlencodedusernamezhangsan&password123登陆响应&#xff1a; 正常对象&#xff1a;正常对象会在数据库中存储&…
阅读更多...
从 vue 源码看问题 — vue 初始化都做了什么事？

从 vue 源码看问题 — vue 初始化都做了什么事？

前言 最近想要对 Vue2 源码进行学习&#xff0c;主要目的就是为了后面在学习 Vue3 源码时&#xff0c;可以有一个更好的对比和理解&#xff0c;所以这个系列暂时不会涉及到 Vue3 的内容&#xff0c;但是 Vue3 的核心模块和 Vue2 是一致的&#xff0c;只是在实现上改变了方式、…
阅读更多...
如何在BSV区块链上实现可验证AI

如何在BSV区块链上实现可验证AI

​​发表时间&#xff1a;2024年10月2日 nChain的顶尖专家们已经找到并成功测试了一种方法&#xff1a;通过区块链技术来验证AI&#xff08;人工智能&#xff09;系统的输出结果。这种方法可以确保AI模型既按照规范运行&#xff0c;避免严重错误&#xff0c;遵守诸如公平、透明…
阅读更多...
MATLAB——矩阵操作

MATLAB——矩阵操作

内容源于b站清风数学建模 数学建模清风老师《MATLAB教程新手入门篇》https://www.bilibili.com/video/BV1dN4y1Q7Kt/ 目录 1.MATLAB中的向量 1.1向量创建方法 1.2向量元素的引用 1.3向量元素修改和删除 2.MATLAB矩阵操作 2.1矩阵创建方法 2.2矩阵元素的引用 2.3矩阵…
阅读更多...
SQL基础—2

SQL基础—2

1.左外连接查询&#xff08;left join on&#xff09; A - A∩B 左外连接查询两张表条件都满足的数据&#xff0c;以及左边表(A表)存在的数据(以左边表为主查询表)。 A - A∩B (A和A交B)。 示例&#xff1a;使用左外连接将dept表作为主查询表&#xff0c;查询员工编号、员工姓…
阅读更多...
【Java并发】乐观锁、悲观锁、CAS、版本号机制

【Java并发】乐观锁、悲观锁、CAS、版本号机制

前言 在现代计算机系统中&#xff0c;处理并发操作时&#xff0c;锁机制是至关重要的。本文将介绍乐观锁、悲观锁以及CAS&#xff08;Compare and Swap&#xff09;这三种常见的并发控制技术&#xff0c;帮助理解它们的原理和应用场景。 1.悲观锁 1.1 定义 悲观锁是一种在访…
阅读更多...
【优选算法】——二分查找！

【优选算法】——二分查找！

目录 1、二分查找 2、在排序数组中查找元素的第一个和最后一个位置 3、搜索插入位置 4、x的平方根 5、山脉数组的封顶索引 6、寻找峰值 7、寻找旋转排序数组中的最小值 8、点名 9、完结散花 1、二分查找 给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组…
阅读更多...
Fooocus图像生成软件本地部署教程：在Windows上快速上手AI创作

Fooocus图像生成软件本地部署教程：在Windows上快速上手AI创作

文章目录 前言1. 本地部署Fooocus图像生成软件1.1 安装方式1.2 功能介绍 2. 公网远程访问Fooocus3. 固定Fooocus公网地址 前言 本篇文章将介绍如何在本地Windows11电脑部署开源AI生图软件Fooocus&#xff0c;并结合Cpolar内网穿透工具轻松实现公网环境远程访问与使用。 Foooc…
阅读更多...
elasticSearch 7.12.1 Docker 安装ik分词

elasticSearch 7.12.1 Docker 安装ik分词

一、下载 https://github.com/infinilabs/analysis-ik/releases/tag/v7.12.1 将文件解压&#xff0c;复制到docker挂载的目录 docker ps#重启docker docker restart f7ec58e91f1f 测试 GET _analyze?pretty {"analyzer": "ik_max_word","text&qu…
阅读更多...
智慧汇聚：十款企业培训工具打造学习型企业

智慧汇聚：十款企业培训工具打造学习型企业

在当今快速变化的商业环境中&#xff0c;企业要想保持竞争力&#xff0c;就必须不断适应新技术、新市场和新的工作方式。构建一个学习型企业&#xff0c;不仅能够促进员工的个人成长&#xff0c;还能增强团队的整体能力和企业的创新能力。为了实现这一目标&#xff0c;借助先进…
阅读更多...
【Searxng】Searxng docker 安装

【Searxng】Searxng docker 安装

SearXNG将用户的查询请求分发至多个支持的搜索引擎&#xff0c;并收集返回的结果进行汇总处理。在这个过程中&#xff0c;它通过内置的过滤器功能屏蔽广告和其他不相关内容&#xff0c;确保搜索结果的纯净度。 一键部署 docker run \--name searxng \-p ????:8080 \-v ~/s…
阅读更多...
FastAPI 请求体解析：基础概念与综合应用

FastAPI 请求体解析：基础概念与综合应用

FastAPI 请求体解析&#xff1a;基础概念与综合应用 本文深入探讨了 FastAPI 中的请求体概念&#xff0c;强调使用 Pydantic 模型来声明请求体数据结构。通过具体示例&#xff0c;展示了如何定义请求体、可选参数及默认值&#xff0c;提升数据验证和类型提示的便利性。文章还说…
阅读更多...
Linux下的Debugfs

Linux下的Debugfs

debugfs 1. 简介 类似sysfs、procfs&#xff0c;debugfs 也是一种内存文件系统。不过不同于sysfs一个kobject对应一个文件&#xff0c;procfs和进程相关的特性&#xff0c;debugfs的灵活度很大&#xff0c;可以根据需求对指定的变量进行导出并提供读写接口。debugfs又是一个Li…
阅读更多...
【论文速读】Optimization-based Prompt Injection Attack to LLM-as-a-Judge

【论文速读】Optimization-based Prompt Injection Attack to LLM-as-a-Judge

基于优化的提示词注入攻击 摘要引言问题描述LLM-as-a-judge威胁模型攻击者知道什么 JUDGEDECEIVER 细节概述生成影子候选回复公式化为优化问题Target-aligned generation lossTarget-enhancement lossAdversarial perplexity loss优化问题 求解优化问题 摘要 LLM-as-a-Judge 利…
阅读更多...
单智能体carla强化学习实战工程介绍

单智能体carla强化学习实战工程介绍

有三个工程&#xff1a; Ray_Carla: 因为有的论文用多进程训练强化学习&#xff0c;包括ray分布式框架等&#xff0c;这里直接放了一个ray框架的示例代码&#xff0c;是用sac搭建的&#xff0c;obs没用图像&#xff0c;是数值状态向量值&#xff08;速度那些&#xff09;。 …
阅读更多...
PD取电快充协议芯片，XSP08Q在灯具中的应用

PD取电快充协议芯片，XSP08Q在灯具中的应用

前言 随着快充技术不断的发展 USB Type-C端口的普及 PD快充成了电子设备中的宠儿&#xff0c;在各种电子设备领域都能见到PD快充的身影&#xff0c;不得不说快充技术的出现让电子设备在充电的速度上得到前所未有的体验&#xff0c;大大的缩短了设备的充电时间。快充协议芯片不…
阅读更多...
最新文章

Copyright @ 2022~2023