logo头像

arthas.com.cn

贪心算法

该文章被围观

本文于493天之前发表,文中内容可能已经过时。

贪心算法简介

贪心算法是指:在每一步求解的步骤中,它要求“贪婪”的选择最佳操作,并希望通过一系列的最优选择,能够产生一个问题的(全局的)最优解。

贪心算法每一步必须满足以下条件:

  • 可行的:即它必须满足问题的约束
  • 局部最优:他是当前步骤中所有可行选择中最佳的局部选择
  • 不可取消:即选择一旦做出,在算法的后面步骤就不可改变了

贪心法在解决问题的策略上目光短浅,仅仅依据当前已有的信息就做出选择,并且一旦做出了选择,无论将来有什么结果,这个选择都不会改变。一句话:不求最优,仅仅求可行解。对于一个详细的问题,怎么知道是否可用贪心算法解此问题,以及是否能得到问题的最优解? 我们能够依据贪心法的2个重要的性质去证明:贪心选择性质和最优子结构性质:

贪心选择

什么叫贪心选择?从字义上就是贪心也就是目光短线。贪图眼前利益。在算法中就是仅仅依据当前已有的信息就做出选择,并且以后都不会改变这次选择。(这是和动态规划法的主要差别)

最优子结构

当一个问题的最优解包括其子问题的最优解时,称此问题具有最优子结构性质。这个性质和动态规划法的一样,最优子结构性质是可用动态规划算法或贪心算法求解的关键特征。

贪心算法案例

1、活动选择问题

这是《算法导论》上的例子,也是一个非常经典的问题。有n个需要在同一天使用同一个教室的活动a1,a2,…,an,教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后,活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠,ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。例如下图所示的活动集合S,其中各项活动按照结束时间单调递增排序。

用贪心法的话思想很简单:活动越早结束,剩余的时间是不是越多?那我就早最早结束的那个活动,找到后在剩下的活动中再找最早结束的不就得了?

java代码实现:

ActiveTime.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public class ActiveTime {
public static void main(String[] args) {
//创建活动并添加到集合中
Active act1 = new Active(1, 4);
Active act2 = new Active(3, 5);
Active act3 = new Active(0, 6);
Active act4 = new Active(5, 7);
Active act5 = new Active(3, 8);
Active act6 = new Active(5, 9);
Active act7 = new Active(6, 10);
Active act8 = new Active(8, 11);
Active act9 = new Active(8, 12);
Active act10 = new Active(2, 13);
Active act11 = new Active(12, 14);
List<Active> actives = new ArrayList<Active>();
actives.add(act1);
actives.add(act2);
actives.add(act3);
actives.add(act4);
actives.add(act5);
actives.add(act6);
actives.add(act7);
actives.add(act8);
actives.add(act9);
actives.add(act10);
actives.add(act11);

List<Active> bestActives = getBestActives(actives, 0, 16);
for (int i = 0; i < bestActives.size(); i++) {
System.out.println(bestActives.get(i));
}
}


/**
*
* @param actives 活动集合
* @param startTime 教室的开始使用时间
* @param endTime 教室的结束使用时间
* @return
*/
public static List<Active> getBestActives(List<Active> actives, int startTime, int endTime) {
//最佳活动选择集合
List<Active> bestActives = new ArrayList<Active>();
//将活动按照最早结束时间排序
actives.sort(null);
//nowTime 用来记录上次活动结束时间
int nowTime = startTime;
/**
* 因为我们已经按照最早结束时间排序,那么只要活动在时间范围内
* actives.get(1)就应当是第一个活动的结束时间.
* 则我们记录第一次活动结束的时间,在结合剩下的活动中,
* 选取开始时间大于nowTime且结束时间又在范围内的活动,则为第二次活动时间,
* 知道选出所有活动
*/
for (int i = 0; i < actives.size(); i++) {
Active act = actives.get(i);
if(act.getStartTime()>=nowTime&&act.getEndTime()<=endTime){
bestActives.add(act);
nowTime = act.getEndTime();
}
}
return bestActives;
}
}

Active.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Active implements Comparable<Active>{
private int startTime;//活动开始时间
private int endTime;//活动结束时间

public Active(int startTime, int endTime) {
super();
this.startTime = startTime;
this.endTime = endTime;
}

public int getStartTime() {
return startTime;
}

public void setStartTime(int startTime) {
this.startTime = startTime;
}

public int getEndTime() {
return endTime;
}

public void setEndTime(int endTime) {
this.endTime = endTime;
}

@Override
public String toString() {
return "Active [startTime=" + startTime + ", endTime=" + endTime + "]";
}

//活动排序时按照结束时间升序
@Override
public int compareTo(Active o) {
if(this.endTime>o.getEndTime()){
return 1;
}else if(this.endTime == o.endTime){
return 0;
}else{
return -1;
}
}
}

运行结果:

1
2
3
4
Active [startTime=1, endTime=4]
Active [startTime=5, endTime=7]
Active [startTime=8, endTime=11]
Active [startTime=12, endTime=14]

2、买彩票的问题

这是leetcode上的一道题:122. 买卖股票的最佳时机 II

题解:只要后一天的价格比之前高就卖出,这样才能赚。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int maxProfit(int[] prices) {
int sum = 0;
for (int i = 0; i < prices.length - 1; i++) {
if (prices[i] < prices[i + 1]) {
sum = sum + prices[i + 1] - prices[i];
}
}
return sum;
}
}

3、分饼干问题

贪心算法通常和排序是分不开的,如果题目给出数组没有排序,我们就需要自己进行排序。

leecode第455题分发饼干

假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子 i ,都有一个胃口值 gi ,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j ,都有一个尺寸 sj 。如果 sj >= gi ,我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

题解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int res = 0;
int i = 0;
int j = 0;
while (i < g.length && j < s.length) {
if (g[i] <= s[j]) {
res++;
i++;
j++;
} else {
j++;
}
}
return res;
}

参考资料

上一篇