贪心算法 Greedy Algorithm

news/2024/9/24 13:18:13/

1) 贪心例子

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

  1. 将寻找最优解的问题分为若干个步骤

  2. 每一步骤都采用贪心原则，选取当前最优解

  3. 因为没有考虑所有可能，局部最优的堆叠不一定让最终解最优

  v2已经不会更新v3因为v3更新过了

算法>贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择，从而希望导致结果是最好或最优的算法。这种算法通常用于求解优化问题，如最小生成树、背包问题等。

算法>贪心算法的应用：

  1. 背包问题：给定一组物品和一个背包，每个物品有一定的重量和价值，要求在不超过背包容量的情况下，尽可能多地装入物品。

  2. 活动选择问题：在一个活动集合中，每次只能参加一个活动，问如何安排时间以最大化所有活动的收益。

  3. 编辑距离问题：给定两个字符串，求它们之间的最小编辑距离(即将一个字符串转换为另一个字符串所需的最少操作次数)。

  4. 网络流问题：给定一张有向图和一些起点和终点，求最大流量。

  5. 找零问题：给定一定数量的硬币和需要找零的金额，求使用最少的硬币数。

常见问题及解答：

  1. 算法>贪心算法一定会找到最优解吗？ 答：不一定。算法>贪心算法只保证在每一步选择中都是最优的，但并不能保证整个问题的最优解。例如，背包问题中的算法>贪心算法可能会导致最后一个物品没有被装入背包。

  2. 如何判断一个问题是否适合用算法>贪心算法解决？ 答：一个问题如果可以用递归的方式分解成若干个子问题，且每个子问题都有明确的最优解(即局部最优),那么这个问题就可以用算法>贪心算法解决。

  3. 算法>贪心算法的时间复杂度是多少？ 答：算法>贪心算法的时间复杂度取决于问题的规模和具体实现。一般来说，对于规模较小的问题，算法>贪心算法的时间复杂度可以达到O(nlogn)或O(n^2);对于规模较大的问题，可能需要O(n^3)或更高。

几个贪心的例子

Dijkstra
// ...
while (!list.isEmpty()) {// 选取当前【距离最小】的顶点Vertex curr = chooseMinDistVertex(list);// 更新当前顶点邻居距离updateNeighboursDist(curr);// 移除当前顶点list.remove(curr);// 标记当前顶点已经处理过curr.visited = true;
}

  • 没找到最短路径的例子：负边存在时，可能得不到正确解

  • 问题出在贪心的原则会认为本次已经找到了该顶点的最短路径，下次不会再处理它（curr.visited = true）

  • 与之对比，Bellman-Ford 并没有考虑局部距离最小的顶点，而是每次都处理所有边，所以不会出错，当然效率不如 Dijkstra

Prim
// ...
while (!list.isEmpty()) {// 选取当前【距离最小】的顶点Vertex curr = chooseMinDistVertex(list);// 更新当前顶点邻居距离updateNeighboursDist(curr);// 移除当前顶点list.remove(curr);// 标记当前顶点已经处理过curr.visited = true;
}
Kruskal
// ...
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

  • 哈夫曼编码

  • 钱币找零，英文搜索关键字

    • change-making problem

    • find Minimum number of Coins

  • 任务编排

  • 求复杂问题的近似解

2) 零钱兑换问题

有几个解（零钱兑换 II）Leetcode 518

[1,2,5]  5  暴力递归

有解：[1, 1, 1, 1, 1]
无解：[1, 1, 1, 1, 2]
无解：[1, 1, 1, 1, 5]
有解：[1, 1, 1, 2]
无解：[1, 1, 1, 5]
无解：[1, 1, 2, 2]
无解：[1, 1, 2, 5]
无解：[1, 1, 5]
有解：[1, 2, 2]
无解：[1, 2, 5]
无解：[1, 5]
无解：[2, 2, 2]
无解：[2, 2, 5]
无解：[2, 5]
有解：[5]
4

public int rec(int index,int[] coins,int remainder){//1.情况1:剩余金额 < 0 - 无解//2.情况2:剩余金额 > 0 - 继续递归//3.情况3:剩余金额 = 0 - 有解if(remainder < 0){return 0;}else if(remainder == 0){return 1;}else{int count = 0;for(int i = index;i<coins.length;i++){count+=rec(i,coins,remainder-coins[i]);}return count;}}

那这个递归是怎么运作的呢?

/*
//第一次传入 index= 0=>1 处理硬币和剩余金额rec(1,5)    remainder > 0 所以走else逻辑 再循环中的递归是多路递归rec(1,4)rec(1,3)rec(1,2)rec(1,1)rec(1,0) <==  1rec(2,-1) <== 0rec(5,-4) <== 0rec(2,0)   <==1rec(5,-3) <== 0rec(2,1)rec(2,-1) <== 0rec(5,-4) <== 0rec(5,-2)  <== 0rec(2,2)rec(2,0)  <== 1rec(5,-3) <== 0rec(5,-1) <== 0rec(2,5-2=3)rec(2,1)rec(2,-1)  <== 0rec(5,-4)  <== 0rec(5,-2)  <==0rec(5,5-5=0) < ==1*/


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.ListIterator;/*** 零钱兑换* 可以凑成总金额所需的所有组合可能数*/
public class Leetcode518 {public int coinChange(int[] coins, int amount) {return rec(0, coins, amount, new LinkedList<>(), true);}/*** 求凑成剩余金额的解的个数** @param index     当前硬币索引* @param coins     硬币面值数组* @param remainder 剩余金额* @param stack     -* @param first     -* @return 解的个数*/public int rec(int index, int[] coins, int remainder, LinkedList<Integer> stack, boolean first) {if(!first) {//第一次不压栈stack.push(coins[index]);}// 情况1：剩余金额 < 0 - 无解int count = 0;if (remainder < 0) {print("无解：", stack);
//            if(!stack.isEmpty()){
//                stack.pop();
//            }}// 情况2：剩余金额 == 0 - 有解else if (remainder == 0) {print("有解：", stack);
//            if(!stack.isEmpty()){
//                stack.pop();
//            }count = 1;}// 情况3：剩余金额 > 0 - 继续递归else {for (int i = index; i < coins.length; i++) {count += rec(i, coins, remainder - coins[i], stack, false);}}if (!stack.isEmpty()) {stack.pop();}return count;}private static void print(String prompt, LinkedList<Integer> stack) {ArrayList<Integer> print = new ArrayList<>();ListIterator<Integer> iterator = stack.listIterator(stack.size());while (iterator.hasPrevious()) {print.add(iterator.previous());}System.out.println(prompt + print);}public static void main(String[] args) {Leetcode518 leetcode = new Leetcode518();
//        int count = leetcode.coinChange(new int[]{1, 5, 10, 25}, 41);
//        int count = leetcode.coinChange(new int[]{25, 10, 5, 1}, 41);
//        int count = leetcode.coinChange(new int[]{5, 2, 1}, 5);int count = leetcode.coinChange(new int[]{1, 2, 5}, 5);
//        int count = leetcode.change(new int[]{15, 10, 1}, 21);System.out.println(count);}
}

但是这个代码放在leetcode上面跑会超时,因为重复处理了很多次相同的操作

我们可以考虑用记忆法 & 动态规划来优化

我们也可以考虑顺序优化 ==>规模下降明显

/*
[5,2,1]   5
rec(5,5)rec(5,0) <== 1rec(2,3) rec(2,1)rec(2,-1) <==0rec(1,0)  <==1rec(1,1)rec(1,0) <==1rec(1,4)rec(1,3)rec(1,2)rec(1,1)rec(1,0) <==1*/

但即使是这样写在leetcode上也是会 StackOverflowError

class Solution {public int change(int amount, int[] coins1) {int[] coins = sort(coins1);return rec(0,coins,amount);}int rec(int index,int[] coins,int remainder){int count = 0;if(remainder == 0){return 1;}else if(remainder<0){return 0;}else{for(int i = index;i<coins.length;i++){count+=rec(index,coins,remainder);}return count;}}/***传入一个有序的数组a(从小到大排序),返回一个从大到小的数组*@param a 传入的数组(有序)*@return 返回一个数组(从大到小)*/int[] sort(int[] a){int[] temp = a;if(temp.length % 2 ==0){//数组里面的个数为偶数for(int i = 0;i<=temp.length/2;i++){int temp1 = a[i];temp[i] = temp[temp.length-1-i];temp[temp.length-1] = temp1;}}else{//数组里面的个数为奇数for(int i = 0;i<temp.length/2;i++){int temp1 = a[i];temp[i]=temp[temp.length-1-i];temp[temp.length-1-i] = temp1;}}return temp;}
}

import java.util.Arrays;public class Main {public static void main(String[] args) {int[] arr = sort(new int[]{1,2,3});System.out.println(Arrays.toString(arr));//为什么我这么选择是因为用Arrays.sort要将数组转化为Integer[]}/***传入一个有序的数组a（从小到大排序），返回一个从大到小的数组* @param a 传入的数组（有序）* @return 返回一个数组（从大到小）*/public static int[] sort(int[] a){int[] temp = a;if(temp.length%2==0){//数组里面的个数为偶数for (int i = 0; i <= temp.length/ 2; i++) {int temp1 = a[i];temp[i]=temp[temp.length-1-i];temp[temp.length - 1-i] = temp1;}}else{//数组里面的个数为奇数for (int i = 0; i < temp.length / 2; i++) {int temp1 = a[i];temp[i]=temp[temp.length-1-i];temp[temp.length - 1-i] = temp1;}}return  temp;}
}

 动态规划->会在动态规划章节说明

最优解（零钱兑换）- 穷举法 Leetcode 322
import java.util.LinkedList;
import java.util.concurrent.atomic.AtomicInteger;public class Leetcode322 {static int min = -1; // 需要的最少硬币数  2 3public int coinChange(int[] coins, int amount) {rec(0, coins, amount, new AtomicInteger(-1), new LinkedList<>(), true);return min;}// count 代表某一组合 钱币的总数 可变的整数对象public void rec(int index, int[] coins, int remainder, AtomicInteger count, LinkedList<Integer> stack, boolean first) {if (!first) {stack.push(coins[index]);}count.incrementAndGet(); // count++if (remainder == 0) {System.out.println(stack);if (min == -1) {min = count.get();} else {min = Integer.min(min, count.get());}} else if (remainder > 0) {for (int i = index; i < coins.length; i++) {rec(i, coins, remainder - coins[i], count, stack, false);}}count.decrementAndGet(); // count--if (!stack.isEmpty()) {stack.pop();}}public static void main(String[] args) {Leetcode322 leetcode = new Leetcode322();
//        int count = leetcode.coinChange(new int[]{5, 2, 1}, 5);int count = leetcode.coinChange(new int[]{25, 10, 5, 1}, 41);
//        int count = leetcode.coinChange(new int[]{2}, 3);
//        int count = leetcode.coinChange(new int[]{15, 10, 1}, 21);System.out.println(count);}
}
最优解（零钱兑换）- 贪心法 Leetcode 322

自己看看就行因为有些测试样例过不了

假定传过来的数据就是从大到小排序,因为java对int数组从大到小排序比较麻烦
public class Leetcode322 {public int coinChange(int[] coins, int amount) {int remainder = amount;int count = 0;for (int coin : coins) {while (remainder - coin > 0) {remainder -= coin;count++;}if (remainder - coin == 0) {remainder = 0;count++;break;}}if (remainder > 0) {return -1;} else {return count;}}public static void main(String[] args) {Leetcode322 leetcode = new Leetcode322();int count = leetcode.coinChange(new int[]{5, 2, 1}, 5);
//        int count = leetcode.coinChange(new int[]{25, 10, 5, 1}, 41);
//        int count = leetcode.coinChange(new int[]{2}, 3);// 问题1 没有回头，导致找到更差的解
//        int count = leetcode.coinChange(new int[]{15, 10, 1}, 21);  // 问题2 没有回头，导致无解
//        int count = leetcode.coinChange(new int[]{15, 10}, 20);  System.out.println(count);}
}


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

相关文章

4月21日，成都Sui Meetup精彩集锦

4月21日，成都Sui Meetup精彩集锦

由 Sui Foundation、开发者教育平台 HackQuest&#xff0c;MoveBit&#xff0c;PoP Planet 共同主办的 Sui 成都开发者茶话会已于 4 月 21 日下午 2:00–6:00 举办&#xff0c;我们诚挚感谢所有对 Sui 生态&#xff0c;Sui Move 语言&#xff0c;和 Web3 开发有兴趣的小伙伴前来…
阅读更多...
Dashboard 介绍

Dashboard 介绍

Dashboard 介绍 一、K8S Dashboard简介 简单的说&#xff0c;K8S Dashboard是官方的一个基于WEB的用户界面&#xff0c;专门用来管理K8S集群&#xff0c;并可展示集群的状态。K8S集群安装好后默认没有包含Dashboard&#xff0c;我们需要额外创建它 二、RABC简介 还是那句话&a…
阅读更多...
WPS文字页面横向

WPS文字页面横向

要将WPS文字页面设置为横向&#xff0c;可以按照以下步骤操作&#xff1a;12 打开WPS文字文档&#xff0c;点击“页面布局”选项卡。在“页面布局”中找到“纸张方向”选项。选择“横向”&#xff0c;这样整篇文档的页面方向就会变为横向。 如果只需要将文档中的特定页面设置…
阅读更多...
vue2/vue3 分别自动暴露 API 接口

vue2/vue3 分别自动暴露 API 接口

思路 遍历当前目录下的所有文件&#xff1b;根据遍历结果循环导出文件名与模块名&#xff1b;将文件名作为前缀&#xff0c;模块名作为实际运用函数或变量&#xff1b;将数据整合&#xff0c;放到新的对象中并导出&#xff1b; vue2 的写法 vue3 的写法 使用 this.loading …
阅读更多...
【Redis 开发】多级缓存，本地进程缓存Caffeine

【Redis 开发】多级缓存，本地进程缓存Caffeine

多级缓存 多级缓存本地进程缓存CaffeineCaffeine三种缓存驱逐策略 多级缓存 Redis处理并发的能力是非常强大的&#xff0c;但是tomcat的支持并发的能力跟不上Redis的性能&#xff0c;导致整体性能的下降 Redis缓存失效时&#xff0c;会对数据库产生冲击&#xff0c;之间再无屏…
阅读更多...
数据结构的队列（c语言版）

数据结构的队列（c语言版）

一.队列的概念 1.队列的定义 队列是一种常见的数据结构&#xff0c;它遵循先进先出的原则。类似于现实生活中排队的场景&#xff0c;最先进入队列的元素首先被处理&#xff0c;而最后进入队列的元素则要等到前面的元素都被处理完后才能被处理。 在队列中&#xff0c;元素只能…
阅读更多...
如何利用 GPT 自我提高写作能力

如何利用 GPT 自我提高写作能力

GPT革命&#xff1a;如何用AI技术重新定义写作 介绍 在我们的数字时代&#xff0c;了解自我提高写作的必要性至关重要。 随着 GPT 的兴起&#xff0c;我们正在见证书写的变革时代。 这篇扩展文章深入探讨了 GPT 如何显着提高写作技能。 拥抱未来&#xff1a; 人工智能时代的写…
阅读更多...
BST二叉搜索树

BST二叉搜索树

概念 二叉搜索树&#xff08;Binary Search Tree&#xff0c;简称BST&#xff09;&#xff0c;又称为二叉排序树或二叉查找树&#xff0c;是一种特殊的二叉树数据结构。它具有以下基本性质&#xff1a; 节点的值的有序性&#xff1a;对于BST中的任意一个节点&#xff0c;其左…
阅读更多...
最新文章

Copyright @ 2022~2023