java贪心算法几个经典例子,活动安排问题的贪心算法Java
00-1010什么是贪婪算法？通过场景理解分析总结算法问题
00-1010分析和解决一个问题时，每一步的计算选择都是最优的或最好的。这样，最终的计算结果有望是最优的。也就是说，算法通过先求局部最优解来求全局最优解。
贪婪算法的基本步骤：
1.首先定义问题，确定问题模型是否适合贪婪算法，即求解最大值问题；
2.对求极值的问题进行反汇编，反汇编后再求解每个子问题，试图得到当前子问题的局部最优解；
3.所有子问题的局部最优解求解后，将这些局部最优解汇总合并得到最终的全局最优解，那么这个最优解就是整个问题的最优解。
00-1010概念性的算法描述可能大家都不太懂，需要用一些实际场景来解释。这里有一个我们童年变化的例子。现在虽然大家都用手机扫一扫，进行支付，已经很久没碰过钱了，但是不妨碍零钱问题帮助我们形象地理解贪婪算法的实现过程。
假设你是一家小店的老板，你有各种面额的零钱，比如1元、3元和5元。这时，一个小孩来买东西。他让你保留最少的零钱，这样他的口袋就能装下了。假设我们将变化分别记录为c[0]，c[1]，c[2].我们记录下孩子们用来买零食的钱的总数。那么我们就可以把孩子想得到最少零钱数的需求转化为一个寻找最优解的编程问题，即给定总数，至少有几个C的和等于给定总数。
示例1:
假设你需要的零钱是11，当前的零钱是1，3，5。
输入：总计=11，c[0]=1，c[1]=3，c[2]=5
输出：3
00-1010通过提取问题中的关键词“最少”，我们可以明确这个问题其实是一个求解最值的问题。只要找到满足条件的最少数量的变更单，就可以解决寻找最少变更的问题。为了找到最少数量的变更单，我们想到的第一个方法是列出一个满足总数11的所有可能变更组合的详尽列表。如下图所示，我们通过寻找变化张数最少的组合，计算出具体的张数，就可以得到最终的答案。但这显然不是一个好办法。如果对应的总数很大，我们穷举列表的结果就会爆炸。
有没有更好的解决办法？这时可以考虑贪婪算法的实现，找到满足要求的最小零钱数。既然是变化，我们可以把问题转化为寻找满足total总量的变化，这至少需要几个步骤。其实就是把问题拆分成每次变化的小步骤，贪婪算法的核心就是在每一个小步骤中贪婪地寻求局部最优解。所以，在每一步的改动中，我们都需要找到对应的最优改动大小。接下来，我们来看看贪婪算法的执行过程。让我们假设这里每种面额都有大量的零钱。
在找零钱的过程中，先得到最大面值为5的零钱(贪心，上来找最大的)，再找到剩下的6=11-5的零钱，这样继续找最大面值为5的零钱(继续贪心)，1=6-5的零钱。此时，我们可以通过获得面值为1的变化来完成任务，然后将前面步骤的结果整合在一起。最后，我们得出，总数为11的最小变化数的大小是3。通过这个分析，贪心算法就没有那么复杂了。
的相应代码实现如下：
/* * * * @作者：沐风* @ date : 2022/5/15 15:33 * @ version : v1。0 .0 * @描述：计算最小满足条件的零钱张数*/public class MinChangeCountSolution { public static void main(String[]args){ int values[]={ 5，5，3，3，1 }；系统。出去。println(getMinChangeCount(11，values))；} //假设价值观念数组从大到小排列static int getMinChangeCount(int total，int[]values){ int rest=total；int result=0；int count=values.length//从大到小遍历所有面值for(int I=0；我数；i) { //计算需要几张这种面值的零钱int need count=rest/values[I]；//计算使用后
的余额 rest -= needCount * values[i]; //计数增加 result += needCount; if (rest == 0) { return result; } } //没有找到合适的面值 return -1; }}以上我们分析了贪心算法的大致实现过程，但是实际上还是有问题的。不知道大家有没有发现，由于贪心算法过于贪心，每一个步骤都想要找到局部最优解。那么假如在上面的例子中，我们没有1块钱的零钱，上述代码的返回结果是-1，即没有符合条件的答案。但是实际并非如此，也就是说5,3,3也是满足条件的，但是上述代码却没有找到。
所以上述代码还是有问题的，关键点就在于，当发现没有1元零钱的时候，需要回头去看能不能把第二步骤中的5元零钱换成3元零钱再进行后续的迭代，如果有这样的步骤，那么就可以找到5,3,3这样的组合。
总结
本文主要通过对于贪心算法的描述，并结合实际的找零钱的例子，带大家一起分析了贪心算法的具体实现过程。同时分析了贪心算法存在的不足，即容易陷入局部最优的陷阱无法自拔，导致最终无法给出满足条件的结果，这也是大家以后在使用贪心算法分析问题时特别需要注意的问题。
到此这篇关于Java贪心算法超详细讲解的文章就介绍到这了,更多相关Java贪心算法内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。