贪心算法

贪心算法详解与例题

之前发过的几个经典算法 :Dijkstra Prim Kruskal 都属于贪心算法。

贪心算法的思想是： 在每一个阶段，可以认为所做的决定是最好的，而不考虑将来的后果，总是做出在当前看来是最好的选择。

这也就是说贪心算法并不从整体最优上加以考虑，它所做出的选择 只是在某种意义上的局部最优选择。

例如 贪心只可以解决背包问题，而不可以解决 0-1背包问题。

我们可以把贪心总结成一句话“眼下能够拿到的就拿”。
下面介绍一些经典的贪心算法（在这里我们只注重算法，对于类只做简单的封装，也不会用到泛型）

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
package greedy;
import java.util.Arrays;
class A{
	public int start;
	public int finish;
	public A(int start,int finish){
		this.start = start;
		this.finish = finish;	
	}
}
/**
 * 类名：GreedySelector
 * 说明：会场安排问题
 * 有n个活动，给出开始和结束时间，场地只有一个，问最大的兼容
 */
public class GreedySelector {
	/**
	 * 方法名：select
	 * 说明：按照结束时间从大到小排序，不断的取结束时间最早的，贪心
	 */
	public static void select(A[] a,boolean[] s,int n){
		s[0] = true;
		int j = 0;
		for(int i = 1; i < n;i++){
			if(a[i].start >a[j].finish){
				j = i;
				s[i] = true;
			}else
				s[i] = false;
		}
		
	}
	/**
	 * 方法名：main
	 * 说明：测试
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//给出的数据按照结束时间非降序排序
		A[] a = new A[11];
		a[0] = new A(1,4);
		a[1] = new A(3,5);
		a[2] = new A(0,6);
		a[3] = new A(5,7);
		a[4] = new A(3,8);
		a[5] = new A(5,9);
		a[6] = new A(6,10);
		a[7] = new A(8,11);
		a[8] = new A(8,12);
		a[9] = new A(2,13);
		a[10] = new A(12,14);
		boolean[] s = new boolean[11];
		select(a,s,11);
		System.out.println(Arrays.toString(s));
	}
}

贪心算法的基本要素：

  1. 贪心选择性质
    是指所求的问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到，这是贪心可行的第一要素，也是其与动规算法的主要区别，在动规中 每步所做的选择往往依赖于相关子问题的解，只有在解出相关子问题后才能做出选择，而贪心则是仅在当前状态下做出的最好选择，即局部最优解。
    一个问题是否具有贪心选择性质必须要证明每一步所做的贪心选择最终导致问题的整体最优解，做了贪心选择后，原问题简化为规模更小的类似子问题
  2. 最优子结构性质
    当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。
    拿活动安排来说，按照结束时间排序，则f[1]为最早结束的，我们选择活动1，那在这之后呢，我们应该是在除去活动1之外的活动里选择结束时间最早的（即在子问题中寻找最优解）。
    对于整个问题的最优解包含子问题的最优解，就说明它具有最优子结构性质。
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
66
67
68
69
70
71
72
73
74
75
/**
 * 文件名：Knapsack.java
 * 时间：2014年11月18日下午8:19:08
 * 作者：修维康
 */
package greedy;
import java.util.Arrays;
class P implements Comparable<P> {
	double w;// 物品的重量
	double p;// 物品的价值
	P(double w, double p) {
		this.w = w;
		this.p = p;
	}
	public double getPrice() {
		return p / w;
	}
	@Override
	public int compareTo(P o) {
		// TODO Auto-generated method stub
		if (this.getPrice() > o.getPrice())
			return -1;
		else if (this.getPrice() < o.getPrice())
			return 1;
		else
			return 0;
	}
}
/**
 * 类名：Knapsack 说明：背包问题。容量为c,w[i]为物品i的重量，p[i]为物品i的价值 问背包能背的最大价值，物品i可切割
 */
public class Knapsack {
	public static double max(P[] ps, double c) {
		Arrays.sort(ps);
		double sum = 0;
		for (int i = 0; i < ps.length; i++) {
			if (c >= ps[i].w) {
				c -= ps[i].w;
				sum += ps[i].p;
			} else {
				sum += ps[i].getPrice() * c;
				break;
			}
		}
		return sum;
	}
	/**
	 * 方法名：main 说明：
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// 按照单位价值排序
		P[] ps = new P[5];
		ps[0] = new P(10,40);
		ps[1] = new P(10,50);
		ps[2] = new P(10,20);
		ps[3] = new P(5,50);
		ps[4] = new P(10,30);
		double c = 30;
		System.out.println(max(ps,c));
	}
}

最优装载问题和 背包问题基本一样，不赘述。

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/**
 * 文件名：HuffmanTree.java
 * 时间：2014年11月18日下午9:39:18
 * 作者：修维康
 */
package greedy;
import java.util.PriorityQueue;
class HuffmanNode implements Comparable<HuffmanNode> {
	public int fre;// 字符频率
	public char key;
	public HuffmanNode left;
	public HuffmanNode right;
	public HuffmanNode(int fre, char key, HuffmanNode left, HuffmanNode right) {
		this.fre = fre;
		this.key = key;
		this.left = left;
		this.right = right;
	}
	@Override
	public int compareTo(HuffmanNode o) {
		// TODO Auto-generated method stub
		if (this.fre > o.fre)
			return 1;
		else if (this.fre < o.fre)
			return -1;
		return 0;
	}
}
/**
 * 类名：HuffmanTree 说明：构造哈夫曼树
 */
public class HuffmanTree {
	/**
	 * 方法名：createHuffmanTree 说明：构造哈夫曼树 返回根节点
	 */
	public static HuffmanNode createHuffmanTree(PriorityQueue<HuffmanNode> p,int n){
		//有N个叶子节点 就要进行N-1次合并
		for(int i = 1;i < n;i++){
			HuffmanNode n1 = p.poll();
			HuffmanNode n2 = p.poll();
			HuffmanNode n3 = new HuffmanNode(n1.fre+n2.fre, ' ', n1, n2);
			p.add(n3);
		}
		return p.poll();
	}
	/**
	 * 方法名：printTree
	 * 说明：先序遍历打印树
	 */
	public static void printTree(HuffmanNode root){
		if(root!=null){
			System.out.println(root.fre);
			printTree(root.left);
			printTree(root.right);
		}
	}
	/**
	 * 方法名：main 说明：测试
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		PriorityQueue<HuffmanNode> p = new PriorityQueue<HuffmanNode>();
		p.add(new HuffmanNode(45, 'a', null, null));
		p.add(new HuffmanNode(13, 'b', null, null));
		p.add(new HuffmanNode(12, 'c', null, null));
		p.add(new HuffmanNode(16, 'd', null, null));
		p.add(new HuffmanNode(9, 'e', null, null));
		p.add(new HuffmanNode(5, 'f', null, null));
		printTree(createHuffmanTree(p,6));
			
	}
}
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package greedy;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
class Job implements Comparable<Job> {
	public int num;// 编号
	public int time;// 处理时间
	public Job(int num, int time) {
		this.num = num;
		this.time = time;
	}
	@Override
	// 按从大到小排序
	public int compareTo(Job o) {
		// TODO Auto-generated method stub
		if (this.time > o.time)
			return -1;
		else if (this.time < o.time)
			return 1;
		return 0;
	}
}
class Machine  implements Comparable<Machine>{
	int num;
	ArrayList<Job> doJob = new ArrayList<Job>();
	private int time = 0;
	public Machine(int num) {
		this.num = num;
	}
	public void add(Job j) {
		doJob.add(j);
		time += j.time;
	}
	public String toString(){
		StringBuffer sb = new StringBuffer();
		sb.append("机器"+num+"处理：");
		for(int i = 0;i < doJob.size();i++)
			sb.append(doJob.get(i).num+"  ");
		return new String(sb);
	}
	@Override
	public int compareTo(Machine o) {
		// TODO Auto-generated method stub
		if(this.time > o.time)
			return 1;
		else if(this.time < o.time)
			return -1;
		return 0;
	}
}
/**
 * 类名：MachinesSched 说明：多机调度算法 有多个作业，有多台机器，作业在完成前不能被打断，作业不能拆分， 给出调度方案
 * 使n个作业尽可能短时间内完成
 */
public class MachinesSched {
	/**
	 * 方法名：allocate 
	 * 按照从大到小的顺序分配给机器，然后机器 按照作业时间进堆，使每次剩下最长作业交给当前时间最短的机器处理
	 */
	public static void allocate(Job[] jobs,PriorityQueue<Machine> p) {
		Arrays.sort(jobs);
		for(int i = 0;i < jobs.length;i++){
			Machine m = p.poll();
			m.add(jobs[i]);
			p.add(m);
		}
	}
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		System.out.println("请输入作业个数：");
		int jobNum = in.nextInt();
		Job[] jobs = new Job[jobNum];
		System.out.println("请输入各个作业时间");
		for(int i = 0;i < jobNum;i++){
			int time = in.nextInt();
			jobs[i] = new Job(i + 1,time);
		}
		System.out.println("请输入机器个数：");
		int machineNum = in.nextInt();
		
		PriorityQueue<Machine> p = new PriorityQueue<Machine>();
		for (int i = 1; i <= machineNum; i++)
		p.add(new Machine(i));
		
		allocate(jobs,p);
		System.out.println(p);
		
	}
}
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
package a;
import java.util.Scanner;
/*
 * 汽车加油问题，一辆汽车加满油可以行驶N公里，在这之间有N个加油站  第N+1为终点， 给出K+1 到K加油站之间的距离 问需要加几次油
 */
public class AddOil {
	public static int howMany(int m,int[] station){
		if(!canArrive(m,station)){
			System.out.println("不能到达");
			return 0;
		}
		int count = 0;
		int full = m;
		for(int i = 0;i < station.length;i++){
			if(m < station[i]){
				count++;
				m = full;
				m -= station[i];
			}
			else{
				m -= station[i];
			}
				
		}
		return count;
	}
	public static boolean canArrive(int m ,int[] station){
		for(int i = 0; i < station.length;i++)
			if(m < station[i])
				return false;
		return true;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		System.out.println("请输入可行驶距离：");
		int m = in.nextInt();
		System.out.println("请输入加油站数量：：");
		
		int n = in.nextInt();
		int[] station = new int[n + 1];
		
		System.out.println("请输入加油站之间的距离：：");
		for(int i = 0;i <= n;i++)
			station[i] = in.nextInt();
		System.out.println(howMany(m,station)+"");
		
	}
}

再加上之前的Dijkstra Prim Kruskal ，和多会场安排问题，都属于贪心的经典题目，贪心专题完.