分析&回答
贪心算法就是遵循某种既定原则,不断地选取当前条件下最优的选择来构造每一个子步骤的解决方案,直到获得问题最终的求解。在对问题求解时,总是做出在当前看最好的选择。也就是说,不从整体最优上考虑,所做的仅是在某种意义上的局部最优解。
利用贪心算法解题,需要解决两个问题:
- 问题是否适合用贪心算法求解所求问题是否具有贪心选择性质
- 贪心选择性质:是指应用同一种规则F,将原问题变为一个相似但规模更小的子问题,后面的每一步都是当前看来最佳的选择。这种选择依赖于已作出的选择,但不依赖与未作出的选择。从全局看,运用贪心策略解决的问题在程序的运行过程中无回溯过程。
- 问题是否具有局部最优解问题具有局部最优解,从而选择一个贪心标准,得到问题的最优解
解题思路:- 建立对问题精确描述的数学模型,包括定义最优解的模型
- 将问题分成一系列子问题,同时定义子问题的最优解结构
- 应用贪心算法可以确定每个子问题局部最优,并根据最优模型,用子问题的局部最优解堆叠出全局最优解
贪心算法解决问题 (种花问题)
假设有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花不能种植在相邻的地块上,它们会争夺水源,两者都会死去。
给你一个整数数组 flowerbed 表示花坛,由若干 0 和 1 组成,其中 0 表示没种植花,1 表示种植了花。另有一个数 n ,能否在不打破种植规则的情况下种入 n 朵花?能则返回 true ,不能则返回 false。
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int count = 0;
int m = flowerbed.length;
int prev = -1;
for (int i = 0; i < m; i++) {
if (flowerbed[i] == 1) {
if (prev < 0) {
count += i / 2;
} else {
count += (i - prev - 2) / 2;
}
if (count >= n) {
return true;
}
prev = i;
}
}
if (prev < 0) {
count += (m + 1) / 2;
} else {
count += (m - prev - 1) / 2;
}
return count >= n;
}
}
贪心算法解决问题 (分发饼干)
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。
对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int numOfChildren = g.length, numOfCookies = s.length;
int count = 0;
for (int i = 0, j = 0; i < numOfChildren && j < numOfCookies; i++, j++) {
while (j < numOfCookies && g[i] > s[j]) {
j++;
}
if (j < numOfCookies) {
count++;
}
}
return count;
}
}
题目代码出自LeetCode,请自行查阅。
反思&扩展
其他应用
- 硬币找零问题
- 活动安排问题
- 课程表
- 哈夫曼编码
喵呜面试助手: 一站式解决面试问题,你可以搜索微信小程序 [喵呜面试助手] 或关注 [喵呜刷题] -> 面试助手 免费刷题。如有好的面试知识或技巧期待您的共享!