关键词:
贪心算法(贪婪算法)
文章目录
贪心算法思想
1.贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。
2.贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素。
3.当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响。贪心算法对每个子问题的解决方案都做出选择,不能回退。
4.贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行,根据某个优化测度,每一步都要确保能获得局部最优解。每一步只考虑一个数据,他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加算法停止。
5.实际上,贪心算法适用的情贪心算法(贪婪算法)况很少。一般对一个问题分析是否适用于贪心算法,可以先选择该问题下的几个实际数据进行分析,就可以做出判断。
该算法存在的问题
1.不能保证求得的最后解是最佳的
2.不能用来求最大值或最小值的问题
3.只能求满足某些约束条件的可行解的范围
选择排序
我们熟知的选择排序,其实采用的即为贪心策略。
它所采用的贪心策略即为每次从未排序的数据中选取最小值,并把最小值放在未排序数据的起始位置,直到未排序的数据为0,则结束排序。
import java.util.Arrays;
/**
* 选择排序
*/
public class TestDemo
public static void swap(int[] arr, int i, int j)
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
public static void selectSort(int[] arr)
//i: 未排序数据的起始位置
for(int i = 0; i < arr.length; ++i)
int minIdx = i;
//从所有未排序的数据中找最小值的索引
for(int j = i + 1; j < arr.length; ++j)
if(arr[j] < arr[minIdx])
minIdx = j;
swap(arr, minIdx, i);
public static void main(String[] args)
int[] arr = 10, 3, 6, 0, 8;
selectSort(arr);
System.out.println(Arrays.toString(arr));
平衡字符串
https://leetcode-cn.com/problems/split-a-string-in-balanced-strings/
在一个 平衡字符串 中,‘L’ 和 ‘R’ 字符的数量是相同的。
给你一个平衡字符串 s,请你将它分割成尽可能多的平衡字符串。
注意:分割得到的每个字符串都必须是平衡字符串,且分割得到的平衡字符串是原平衡字符串的连续子串。
返回可以通过分割得到的平衡字符串的 最大数量 。
输入:s = "RLLLLRRRLR"
输出:3
解释:s 可以分割为 "RL"、"LLLRRR"、"LR"
,每个子字符串中都包含相同数量的 ‘L’ 和 ‘R’ 。
解题思路: 不要有嵌套的平衡,只要达到平衡,就立即分割(贪心策略).我们假设 ‘R’ == 1, ‘L’ == -1 .只要累加等于 0 就算分割一次.
class Solution
public int balancedStringSplit(String s)
int cnt = 0;
int balance = 0;
for(int i = 0; i < s.length(); i++)
if(s.charAt(i) == 'L')
balance--;
if(s.charAt(i) == 'R')
balance++;
if(balance == 0)
cnt++;
return cnt;
买卖股票的最佳时机
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。
在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。
返回 你能获得的 最大 利润 。
class Solution
public int maxProfit(int[] prices)
int ret = 0;
for(int i = 1; i < prices.length; ++i)
int curProfit = prices[i] - prices[i - 1];
if(curProfit > 0)
ret += curProfit;
return ret;
跳跃游戏
https://leetcode-cn.com/problems/jump-game/
给定一个非负整数数组 nums
,你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
贪心策略
设想一下,对于数组中的任意一个位置 y,我们如何判断它是否可以到达?根据题目的描述,只要存在一个位置 x,它本身可以到达,并且它跳跃的最大长度为 x + nums[x]
,这个值大于等于 y,即 x+nums[x] ≥ y
,那么位置y也可以到达。
这样以来,我们依次遍历数组中的每一个位置,并实时维护最远可以到达的位置。对于当前遍历到的位置x,如果它在 最远可以到达的位置的范围内,那么我们就可以从起点通过若干次跳跃到达该位置,因此我们可以x+nums[x]
更新 最远可以到达的位置。
在遍历的过程中,如果最远可以到达的位置大于等于数组中的最后一个位置,那就说明最后一个位置可达,我们就可以直接返回True作为答案。反之,如果在遍历结束后,最后一个位置仍然不可达,我们就返回 False 作为答案。
/**
* 跳跃位置
*/
public class TestDemo3
public class Solution
public boolean canJump(int[] nums)
int pos = nums.length - 1;
int rightmost = 0;
for (int i = 0; i <= pos; ++i)
//如果可以到达当前位置,则更新最大
if (i <= rightmost)
//每次更新最大的位置
rightmost = Math.max(rightmost, i + nums[i]);
//如果可以到达最后一个位置,则直接返回
if (rightmost >= pos)
return true;
return false;
钱币找零
假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6
张。现在要用这些钱来支付K元,至少要用多少张纸币?
贪心策略: 用贪心算法的思想,很显然,每一步尽可能用面值大的纸币即可.
import java.util.Scanner;
/**
* 纸币找零
*/
public class TestDemo4
public static int solve(int money, int[][] moneyCount)
int num = 0;
//首先选择最大面值的纸币
for (int i = moneyCount.length - 1; i >= 0; i--)
//需要的当前面值与面值数量取最小
int c = Math.min(money / moneyCount[i][0], moneyCount[i][1]);
money = money - c * moneyCount[i][0];
num += c;
if (money > 0)
num = -1;
return num;
public static void main(String[] args)
//存放纸币与数量: first:纸币,second:数量
int[][] moneyCount = 1, 3 , 2, 1 , 5, 4 , 10, 3 , 20, 0
,50, 1, 100, 10 ;
Scanner scanner = new Scanner(System.in);
int money;
System.out.println("请输入要支付的钱");
money = scanner.nextInt();
int res = solve(money, moneyCount);
if (res != -1)
System.out.println(res);
else
System.out.println("No");
多机器调度问题
某工厂有n个独立的作业,由m台相同的机器进行加工处理。作业i所需的加工时间为ti,任何作业在被处理时不能中断,也不能进行拆分处理。现厂长请你给他写一个程序:算出n个作业由m台机器加工处理的最短时间
输入:
第一行T(1<T<100)表示有T组测试数据。每组测试数据的第一行分别是整数n,m(1<=n<=10000,
1<=m<=100),接下来的一行是n个整数ti(1<=t<=100)。
输出: 所需的最短时间
贪心策略: 每次选取剩余作业中执行时间最长的,然后分别优先给先完成的机器分配新的任务
import java.util.Arrays;
import java.util.Scanner;
/**
*多机器调度问题
*/
public class TestDemo5
public static int findMax(int[] machines)
int ret = machines[0];
for (int cur : machines)
if (ret < cur)
ret = cur;
return ret;
private static int greedStrategy(int[] taskTime, int m)
int n = taskTime.length;
// 按作业时间从小到大排序
Arrays.sort(taskTime);
int[] machines = new int[m];
// 作业数如果小于机器数,直接返回最大的作业时间
if (n <= m)
return taskTime[n-1];
else
for (int i = n-1; i >= 0; --i)
// 找到最先结束的机器,分配新的任务
int finish = 0;
//首先假设用第一个机器处理
int machineTime = machines[finish];
// 从剩余机器中选择作业时间最小的
for (int j = 1; j < m; j++)
if (machineTime > machines[j])
finish = j;
machineTime = machines[j];
// 将新的任务分配给最先结束的机器执行
machines[finish] += taskTime[i];
// 从所有机器中选出最后执行完作业的机器
return findMax(machines);
public static void main(String[] args)
int n, m;
System.out.println("请输入作业个数和机器数");
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
System.out.println("输入任务的时间");
int[] taskTime = new int[n];
for (int i = 0; i < n; ++i)
taskTime[i] = scanner.nextInt();
System.out.println("最短的时间" + greedStrategy(taskTime,m));
举办活动数量最多
有n个需要在同一天使用同一个教室的活动 a1, a2
, …, an,教室同一时刻只能由一个活动使用。每个活动a[i]都有一个开始时间s[i]和结束时间f[i]。一旦被选择后,活动a[i]就占据半开时间区间[s[i],f[i])。如果[s[i],f[i])和[s[j],f[j])互不重
叠,a[i]和a[j]两个活动就可以被安排在这一天。求使得尽量多的活动能不冲突的举行的最大数量。
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
/**
* 举办活动数量最多的
*/
class myComparator implements Comparator<int[]>
//按起点递增排序
public int compare(int[] a, int[] b)
return a[1] - b[1];
public class TestDemo6
public static int greedyActivitySelector(int[][] act)
//贪婪策略:每次选择最早结束的活动
int num = 1, i = 0;
for (int j = 1; j < act.length; j++)
if (act[j][0] >= act[i][1])
i = j;
num++;
return num;
public static void main(String[] args)
Scanner scanner = new Scanner(System.in);
int number = scanner.nextInt();
int[][] act = new int[number][2];
for (int i = 0; i < act.length; ++i)
act[i][0] = scanner.nextInt();
act[i][1] = scanner.nextInt();
//按照活动截止时间从小到大排序
Arrays.sort(act, new myComparator());
int ret = greedyActivitySelector(act);
System.out.println(ret);
无重叠区间
https://leetcode-cn.com/problems/non-overlapping-intervals/
给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。
解法1: 先求出能得到最多的数量(上一题举办活动数量最多的思路),再总数相减,得到需要移除数量最少的值
class myComparator implements Comparator<int[]>
//按最早结束递增排序
public int compare(int[] a, int[] b)
return a[1] - b[1];
class Solution
public int eraseOverlapIntervals(int[][] intervals)
if (intervals.length == 0)
return 0;
//按照结束进行递增排序
Arrays.sort(intervals, new myComparator());
//贪婪策略:每次选择最早结束的活动
int num = 1, i = 0;
for (int j = 1; j < intervals.length; j++)
if (intervals[j][0] >= intervals[i][1])
i = j;
num++;
return intervals.length - num;
解法2:
class myComparator implements Comparator<int[]>
//按起点递增排序
public int compare(int[] a, int[] b)
return a[0] - b[0];
class Solution
public int eraseOverlapIntervals(int[][] intervals)
if (intervals.length == 0)
return 0;
//按照起始进行递增排序
Arrays.sort(intervals, new myComparator());
//贪婪策略:每次选择最早结束的活动
int num = 0, i = 0;
for (int j = 1; j < intervals.length; j++)
if (intervals[j][0] >= intervals[i][1])
//下一场活动开始时间大于等于上一场活动结束时间
//不需要更新
i = j;
else
if(intervals[j][<贪心算法(代码片段)
贪婪算法贪心算法(GreedyAlgorithm)简介贪心算法,又名贪婪法,是寻找最优解问题的常用方法,这种方法模式一般将求解过程分成若干个步骤,但每个步骤都应用贪心原则,选取当前状态下最好/最优的选择(局部最有利的选择)... 查看详情
贪心算法(代码片段)
Java实现贪心算法(找零钱问题)1packagecom.java;23importjava.util.Random;4/**5*贪心算法6*贪心算法,又称贪婪算法,是指在对问题求解时,总是做出在当前看来是最好的选择。7*也就是说,不从整体最优解出发来考虑,它所做出的仅是在... 查看详情
贪心算法回顾(代码片段)
各位好,贪心算法可以说是处处学到,被面试频频问道,接下来回顾以下,并上代码: 1packagecom.clb.ai.algorithm;23importjava.util.ArrayList;4importjava.util.List;5importjava.util.Map;6importjava.util.TreeMap;78/**9*贪心算法(又称贪婪算法)是指,在... 查看详情
贪婪法——————贪心算法
...開始看王晓华写的《算法的乐趣》,把它当做教材。看到贪心算法,由于大一的时候C语言没学好,所以作者写的C实现代码不是看得非常懂。可是基本思想还是可以掌握的。接下来我总结一下我今天学到的贪心算法:贪心算法是... 查看详情
[数据结构]贪婪算法(dijkstraalgorithm)(代码片段)
...只讲贪婪算法啦,一会再开一篇。一、贪婪算法简介贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑, 查看详情
背包问题(贪心算法)(代码片段)
贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。 贪心算法还是比较好理解的一个算法,以前我也... 查看详情
小白带你学系列---贪心算法(代码片段)
贪心算法(GreedyAlgorithm)简介贪心算法,又名贪婪法,是寻找最优解问题的常用方法,这种方法模式一般将求解过程分成若干个步骤,但每个步骤都应用贪心原则,选取当前状态下最好/最优的选择(局部最有利的选择),并... 查看详情
chatgpt教你算法——贪心算法(代码片段)
0.引言在计算机科学中,贪心算法是一种用来解决多阶段决策最优化问题的算法。它的名字来源于贪婪策略,即每一步都选择当前看来是最优的选择,而不考虑未来的影响。这种算法的优点在于它的简单性和速度,... 查看详情
贪心算法(代码片段)
1、贪心算法介绍 贪心算法,又称贪婪法,是寻找最优解算法的常用算法。当面对没有快速算法的问题(NP完全问题)时,贪心算法则可以化解危机,这种方法的模式一般是将问题求解分割成若干步骤,... 查看详情
贪心算法
贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择的算法。即不从整体最优上加以考虑,它所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,关键是... 查看详情
算法图解-贪婪算法(代码片段)
内容:如何处理不可能完成的任务;没有快速算法的问题(NP完全问题)学习是被NP完全问题,以免浪费时间去寻找解决他们的快速算法学习近似算法,使用它们可快速中找到NP完全问题的近似解学习贪婪策略——一种非常简单的... 查看详情
贪婪算法(代码片段)
贪婪算法:这是一种近似算法(approximationalgorithm)。在获得精确解需要的时间太长时,可使用近似算法。判断近似算法优劣的标准如下:?速度有多快;?得到的近似解与最优解的接近程度。贪婪算法是不错的选择,它们不仅简单... 查看详情
贪心算法(代码片段)
贪心算法1.算法介绍贪心算法是指在可对问题进行求解时,在每一步中采用最好或者最优的选择,从而导致结果最好的算法贪心算法得到的结果不一定是最优的结果,但是都是相对近似最优解的结果2.实际问题广播台覆盖地区k1“... 查看详情
贪心算法(代码片段)
介绍:贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,关... 查看详情
贪心算法(代码片段)
Wiki关于算法的定义贪心算法(英语:greedyalgorithm),又称贪婪算法,是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法。[1]比如在旅行推销员问题中,如果旅行... 查看详情
贪心算法例题(代码片段)
目录贪心算法找零问题最大的金额堆果子贪心算法 贪心算法(greedyalgorithm,又称贪婪算法)是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考... 查看详情
《算法图解》——第八章贪婪算法(代码片段)
第八章 贪婪算法1 简单的贪婪算法每步都采取最优的做法,每步都选择局部最优解。 2 背包问题有些情况下,完美是优秀的敌人。如果你只需要找到一个大致解决问题的算法,贪婪算法挺... 查看详情
贪心算法回顾(代码片段)
各位好,贪心算法可以说是处处学到,被面试频频问道,接下来回顾以下,并上代码: 1packagecom.clb.ai.algorithm;23importjava.util.ArrayList;4importjava.util.List;5importjava.util.Map;6importjava.util.TreeMap;78/**9*贪心算法(又称贪婪算法)是指,在... 查看详情