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

news/2024/11/6 23:05:11/

贪心算法

1)Greedy algorithm

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

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

贪心算法例子

Dijkstra

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

prim

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

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

KrusKal

java">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

递归实现

java">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

递归实现

java">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));}
}

贪心实现

java">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上跑，有些测试用例是不能通过。

动态规划实现

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

java">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树完成
java">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;}@Overridepublic 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 字符串编码后占几个bitint sum = dfs(root, new StringBuilder());		// 得到字符串编码后占的bitfor(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个活动

  • 每个活动有它们各自的起始和结束时间
  • 找出时间上不冲突的活动组合，能够最充分利用会议室(举办的活动次数最多)
java">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;}@Overridepublic 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

无重叠区间

java">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. 每次可以不拿，全拿，拿一部分，问最高价值是多少
    在这里插入图片描述
java">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;}@Overridepublic 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. 每次可以不拿或者全拿，问最高价值是多少
java">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;}@Overridepublic 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

贪心算法局限性

在这里插入图片描述


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

相关文章

Chrome与夸克的安全性对比

Chrome与夸克的安全性对比

在当今数字化时代&#xff0c;浏览器的安全性对于用户来说至关重要。Chrome和夸克作为两款流行的浏览器&#xff0c;各有其特点和优势。本文将对这两款浏览器的安全性进行详细对比&#xff0c;帮助用户更好地了解它们之间的差异。&#xff08;本文由https://www.chromegw.com/的…
阅读更多...
深入浅出 Spring Boot 与 Shiro：构建安全认证与权限管理框架

深入浅出 Spring Boot 与 Shiro：构建安全认证与权限管理框架

一、Shiro框架概念 &#xff08;一&#xff09;Shiro框架概念 1.概念&#xff1a; Shiro是apache旗下一个开源安全框架&#xff0c;它对软件系统中的安全认证相关功能进行了封装&#xff0c;实现了用户身份认证&#xff0c;权限授权、加密、会话管理等功能&#xff0c;组成一…
阅读更多...
基于python主观题自动阅卷系统毕业设计项目

基于python主观题自动阅卷系统毕业设计项目

基于python主观题自动阅卷系统毕业设计项目 大家好&#xff0c;我是陈辰学长&#xff0c;一名在 Java 圈辛勤劳作的码农。今日&#xff0c;要和大家分享的是一款基于python主观题自动阅卷系统毕业设计。项目源码以及部署相关事宜&#xff0c;请联系陈辰学长&#xff0c;文末会…
阅读更多...
opencv保姆级讲解-guI和pymsql实现人脸识别打卡（6）

opencv保姆级讲解-guI和pymsql实现人脸识别打卡（6）

PySimpleGUI 库 ​ PySimpleGUI 是一个用于简化 GUI 编程的 Python 包&#xff0c;它封装了多种底层 GUI 框架&#xff08;如 tkinter、Qt、WxPython 等&#xff09;&#xff0c;提供了简单易用的 API。PySimpleGUI 包含了大量的控件&#xff08;也称为小部件或组件&#xff0…
阅读更多...
VMware虚拟机-Ubuntu设置共享文件夹

VMware虚拟机-Ubuntu设置共享文件夹

VMware虚拟机-Ubuntu设置共享文件夹&#xff08;超详细&#xff09;_vmware ubuntu共享文件夹-CSDN博客
阅读更多...
scala学习记录，Set，Map

scala学习记录，Set，Map

set&#xff1a;集合&#xff0c;表示没有重复元素的集合&#xff0c;特点&#xff1a;唯一 语法格式&#xff1a;val 变量名 Set [类型]&#xff08;元素1&#xff0c;元素2...&#xff09; 可变不可变 可变&#xff08;mutable&#xff09;可对元素进行添加&#xff0c;删…
阅读更多...
【安当产品应用案例100集】029-使用安全芯片保护设备核心业务逻辑

【安当产品应用案例100集】029-使用安全芯片保护设备核心业务逻辑

我国工业企业普遍缺乏数据安全意识&#xff0c;对数据安全保护缺乏基本认识。这导致企业在数据安全方面的投入不足&#xff0c;保护能力基本不具备&#xff0c;难以有效应对数据安全风险。不过随着安全事件越来越多&#xff0c;很多工业企业的安全意识也越来越高&#xff0c;在…
阅读更多...
常见的排序算法（二）

常见的排序算法（二）

归并排序 归并排序&#xff08;Merge Sort&#xff09;是一种基于分治法&#xff08;Divide and Conquer&#xff09;的排序算法。它将一个大的问题分解成小的问题&#xff0c;然后递归地解决这些小问题&#xff0c;最后合并&#xff08;merge&#xff09;得到最终的排序结果。…
阅读更多...
最新文章

Copyright @ 2022~2023