贪心策略算法例题

发表于 | 更新于 | 分类于 | 阅读次数： | 字数： 4,001 | 阅读时长： 19

贪心算法简介：贪心算法

硬币支付问题：

有1元,5元,10元,50元,100元,500元的硬币各c1,c5,c10,c50,c100,c500枚.

现在要用这些硬币来支付A元,最少需要多少枚硬币?

假定本题至少存在一种支付方案.

0≤ci≤10^9

0≤A≤10^9

输入:

第一行有六个数字,分别代表从小到大6种面值的硬币的个数

第二行为A,代表需支付的A元

样例:

输入

3 2 1 3 0 2
620

输出

6

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
import java.util.Scanner;

public class 硬币问题 {
	static int[] coins = {1, 5, 10, 50, 100, 500};
	static int[] coinsCount;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		coinsCount = new int[6];
		for(int i = 0; i < 6; i++) {
			coinsCount[i] = sc.nextInt();
		}
		int A = sc.nextInt();
		int res = f(A, 5);
		System.out.println(res);
		
	}

	private static int f(int A, int cur) {
		if(A <= 0) return 0;
		if(A == 0) return A;
		int num = A / coins[cur]; //计算最大硬币需要多少个
		int t = Math.min(num, coinsCount[cur]);//看当前面值的硬币是否够，选取较少的数量
		return t + f(A - t * coins[cur], cur - 1);
	}
}

程序运行结果：

1
2
3
3 2 1 3 0 2  //输入
620
6 //输出

快速渡河问题：

原题：

A group of N people wishes to go across a river with only one boat, which can at most carry two persons.
Therefore some sort of shuttle arrangement must be arranged in order to row the boat back and forth so that all people may cross.
Each person has a different rowing speed; the speed of a couple is determined by the speed of the slower one.
Your job is to determine a strategy that minimizes the time for these people to get across.

Input

The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases.
Then T cases follow.
The first line of each case contains N, and the second line contains N integers giving the time for each people to cross the river.
Each case is preceded by a blank line. There won’t be more than 1000 people and nobody takes more than 100 seconds to cross.

Output

For each test case, print a line containing the total number of seconds required for all the N people to cross the river.

Sample Input
1
4
1 2 5 10
Sample Output
17

翻译：

一群人想用一条船过河，而这条船最多只能载两个人。。

因此，必须安排某种穿梭安排，使船来回划行，以便所有人都能通过。

每个人划桨的速度不同;两人一组划行，速读由慢的决定。

你的工作是确定一个策略，使这些人的用最少的时间把人送过去。

输入

输入的第一行包含一个整数T (1 <= T <= 20)，即测试用例的数量。

然后T个例子。

每种情况的第一行包含N，第二行包含N个整数，给出每个人过河的时间。

每个case前面都有一个空行。不会有超过1000人，没有人需要超过100秒的时间通过。

输出

对于每个测试用例，打印一行包含所有N个人过河所需的总秒数。

样例输入

1
2
3
4
> 1
> 4
> 1 2 5 10
>

样例输出

17

解题思路：

利用贪心算法思想。

过河有两种最优策略：加入有4个人。

  • 情况1 ：1， 2 出发，1返回，最后两名出发，2返回，剩余两名过河
  • 情况2: 1,3出发，1返回，1、4出发，1返回，1、2过河

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
import java.util.Arrays;
import java.util.Scanner;

public class 快速渡河问题 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for(int i = 0; i < t; i++) {
			int n = sc.nextInt();
			int[] speed = new int[n];
			for(int j = 0; j < n; j++) {
				speed[j] = sc.nextInt();
			}
			Arrays.sort(speed);
			f(n, speed);
		}
	}
	
	public static void f(int n, int[] speed) {
		int left = n;
		int ans = 0;
		while(left > 0) {
			if(left ==1 ) {//只有一人
				ans += speed[0];
				break;
			}else if(left == 2) {//只有两人
				ans += speed[1];
				break;
			}else if(left == 3) {//只有三人
				ans += speed[2] + speed[0] + speed[1];
				break;
			}else {
				//情况1 ：1， 2 出发，1返回，最后两名出发，2返回
				int s1 = speed[1] + speed[0] + speed[left - 1] + speed[1];
				//情况2: 1,3出发，1返回，1、4出发，1返回，1、2过河
				int s2 = speed[left - 1] + speed[0] * 2 +speed[left - 2]; 
				ans += Math.min(s1, s2);
				left -= 2;//左侧是渡河的起点，left代表左侧的剩余人数。
			}
		}
		System.out.println(ans);
	}
}

程序运行结果：

1
2
3
4
1
4
1 2 5 10 //输入
17 //输出

区间调度问题：

有n项工作,每项工作分别在si时间开始,在ti时间结束.

对于每项工作,你都可以选择参与与否.如果选择了参与,那么自始至终都必须全程参与.

此外,参与工作的时间段不能重复(即使是开始的瞬间和结束的瞬间的重叠也是不允许的).

你的目标是参与尽可能多的工作,那么最多能参与多少项工作呢?

1≤n≤100000

1≤si≤ti≤10^9

输入:

第一行:n
第二行:n个整数空格隔开,代表n个工作的开始时间
第三行:n个整数空格隔开,代表n个工作的结束时间

样例输入:

5
1 3 1 6 8
3 5 2 9 10

样例输出:

3

说明:选取工作1,3,5

解题思路：

以结束时间从早到晚排序，然后开始选择。

选择最早结束的任务后，判断下一个任务的开始时间是否大于该任务的结束时间，如果大于，证明没重复，可以做。否则，因为任务时间重叠，放弃该任务。

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
import java.util.Arrays;
import java.util.Scanner;

public class 区间调度问题 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] beginTime = new int[n];
		for(int i = 0; i < n; i++) {
			beginTime[i] = sc.nextInt();
		}
		int[] endTime = new int[n];
		for(int i = 0; i < n; i++) {
			endTime[i] = sc.nextInt();
		}
		Job[] jobs = new Job[n];
		for(int i = 0; i < n; i++) {
			jobs[i] = new Job(beginTime[i], endTime[i]);
		}
		Arrays.sort(jobs);
		int res = f(n, jobs);
		System.out.println(res);
	}
	
	private static int f(int n, Job[] jobs) {
		int count = 1;
		int y = jobs[0].endTime;//第一个任务必选，结束时间最早的。
		for(int i = 0; i < n; i++) {
			if(jobs[i].beginTime > y){//如果开始时间大于上一个任务的结束时间
				count++; //计数加1
				y = jobs[i].endTime; //更新任务的结束时间
			}
		}
		return count;
	}

	//封装开始时间和结束时间，进行自定义排序
	public static class Job implements Comparable<Job> {

		int beginTime;
		int endTime;
		
		public Job(int beginTime, int endTime) {
			this.beginTime = beginTime;
			this.endTime = endTime;
		}
		//自定义排序规则
		@Override
		public int compareTo(Job other) {
			int x = this.endTime - other.endTime;
			if(x == 0){
				return this.beginTime - other.beginTime;
			}else {
				return x;
			}
		}
		
	}
}

程序运行结果：

1
2
3
4
5
1 3 1 6 8
3 5 2 9 10 //输入
3  //输出

区间选点问题：

Intervals
You are given n closed, integer intervals [ai, bi] and n integers c1, …, cn.
Write a program that:
reads the number of intervals, their end points and integers c1, …, cn from the standard input,
computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,…,n,
writes the answer to the standard output.

Input
The first line of the input contains an integer n (1 <= n <= 50000) – the number of intervals.
The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai,
bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.

Output
The output contains exactly one integer equal to the minimal size of set Z
sharing at least ci elements with interval [ai, bi], for each i=1,2,…,n.
Sample Input
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
Sample Output
6

翻译：

间隔

你得到了n闭的,整数区间[ai,bi]和n个整数c1,…cn。

编写一个程序:

读取间隔的次数,它们的端点和整数c1,…,cn从标准输入,

计算一个集合Z的最小大小,它至少有ci的常见元素[ai,bi],每个i = 1,2,…,

写出标准输出的答案。

输入

输入的第一行包含整数n(1 < = n < = 50000)——间隔数。

下面的n行描述间隔。(i + 1)-输入的第一行包含三个整数ai,

bi和ci被单个空间分隔,从而使0 < = ai < = all(= 50000)和1 < = bi - ai + 1。

输出

输出包含一个等于设置Z最小大小的一个整数

至少分享ci元素的区间[ai,bi],每一个i = 1,2,…,n。

样本输入

1
2
3
4
5
6
7
> 5
> 3 7 3
> 8 10 3
> 6 8 1
> 1 3 1
> 10 11 1
>

样品输出

6

解题思路：

这里使用了贪心的算法。

首先和上题一样，按照结束时间从早到晚排序。

然后从早到晚，在结束点标记，检查是否满足该区间的标记个数，如果不满足，从结束时间向前标记。

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
66
67
68
69
70
import java.util.Arrays;
import java.util.Scanner;

public class 区间选点1 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Interval[] intervals = new Interval[n];
		for(int i = 0; i < n; i++) {
			intervals[i] = new Interval(sc.nextInt(), sc.nextInt(), sc.nextInt());
		}
		Arrays.sort(intervals);//按区间右端点排序
		
		int max = intervals[n - 1].t; //右端最大值
		int[] axis = new int[max + 1];//标记数轴上的点是否被选中
		for(int i = 0; i < n; i++) {
			//1.查询区间中有多少个点
			int s = intervals[i].s;//起点
			int t = intervals[i].t; //终点
			int cnt = sum(axis, s, t); //axis[t] - axis[s - 1]，效率低
			//2.如果不够，从区间右端点开始标记，遇到标记过的点就跳过
			intervals[i].c -= cnt;
			while (intervals[i].c > 0) {
				if(axis[t] == 0) {
					axis[t] = 1;
					intervals[i].c--;
					t--;
				}else {
					t--;
				}
			}
		}
		//输出点的个数
		int point = 0;
		for(int i = 0; i < axis.length; i++) {
			point += axis[i];
		}
		System.out.println(point);
	}
	
	private static int sum(int[] axis, int s, int t) {
		int count = 0;
		for(int i = s; i <= t; i++) {
			count += axis[i];
		}
		return count;
	}

	public static class Interval implements Comparable<Interval>{
		int s;
		int t;
		int c;
		public Interval(int s, int t, int c) {
			this.s = s;
			this.t = t;
			this.c = c;
		}
		
		@Override
		public int compareTo(Interval other) {
			int x = this.t - other.t;
			if(x == 0) {
				return this.s - other.s;
			}else {
				return x;
			}
		}		
	}
}

程序运行结果：

1
2
3
4
5
6
7
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1 //输入
6   //输出

字典序最小问题：

给一个定长为N的字符串S,构造一个字符串T,长度也为N。

起初，T是一个空串，随后反复进行下列任意操作

  1. 从S的头部删除一个字符，加到T的尾部
  2. 从S的尾部删除一个字符，加到T的尾部

目标是最后生成的字符串T的字典序尽可能小

1≤N≤2000
字符串S只包含大写英文字母

输入：字符串S
输出：字符串T

例如：输入

1
2
3
4
5
6
7
8
> 6
> A
> C
> D
> B
> C
> B
>

输出：

1
2
> ABCBCD
>

解题思路：

利用贪心算法。

每次比较S的要取的首部和尾部字符大小，谁小就将谁加到T中。如过相同比较各自的下一个。

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
import java.util.Scanner;

public class 字典序最小 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		StringBuilder  sb = new StringBuilder();
		for(int i = 0; i < n; i++) {
			sb.append(sc.next());
		}
		char[] S = sb.toString().toCharArray();
		System.out.println(sb.toString());
		f(S, n);
	}

	private static void f(char[] s, int n) {
		int begin = 0;
		int end = n - 1;
		char[] T = new char[n];
		int i = 0;
		while(begin <= end) {
			if(s[begin] < s[end]) {
				T[i++] = s[begin++]; 
			}else if(s[begin] > s[end]){
				T[i++] = s[end--];
			}else {
				if(s[begin+1] <= s[end-1] && begin <= end) {
					T[i++] = s[begin++]; 
				}else{
					T[i++] = s[end--];
				}
			}
		} 
	}
}

最优转载问题：

给出n个物体，第i个物体重量为wi。选择尽可能多的物体，使得总容量不超过C。

输入：

第一行：物体个数n。接下来输入每个物体的重量。最后输入C。

输入：最多装入的个数。

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
import java.util.Arrays;
import java.util.Scanner;

public class 最优装载问题 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] w = new int[n];
		for(int i = 0; i < n; i++) {
			w[i] = sc.nextInt();
		}
		int C = sc.nextInt();
		Arrays.sort(w);
		int ans = f(n, w, C);
		System.out.println(ans);
	}

	private static int f(int n, int[] w, int c) {
		int sum = 0;
		int cnt = 0;
		for(int i = 0; i < n; i++) {
			sum += w[i];
			if(sum <= c) {
				cnt++;
			}else {
				break;
			}
		}
		return cnt;
	}
}

部分背包问题：

有n个物体，第i个物体的重量为wi，价值为vi。在总重量不超过C的情况下让总价值尽量高。

每一个物体都可以只取走一部分，价值和重量按比例计算。

求最大总价值

注意：每个物体可以只拿一部分，因此一定可以让总重量恰好为C。

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
import java.util.Arrays;
import java.util.Scanner;

public class 部分背包问题 {

	public static void main(String[] args) {
		int[] w = {1, 2, 3, 4, 5};
		int[] v = {3, 4, 3, 1, 4};
		int n = w.length;
		double C = 10;
		Obj[] objs = new Obj[n];
		for(int i = 0; i < n; i++) {
			objs[i] = new Obj(w[i], v[i]);
		}
		Arrays.sort(objs);
		double c = C;
		double maxValue = 0;
		for(int i = n - 1; i > 0; i--) {
			if(objs[i].w <= c) {
				maxValue += objs[i].v;
				c -= objs[i].w;
			}else {
				maxValue += objs[i].v * (c / objs[i].w);
				break;
			}
		}
		System.out.println(maxValue);
	}
	
	private static class Obj implements Comparable<Obj>{
		int w;
		int v;
		public Obj(int w, int v) {
			this.w = w;
			this.v = v;
		}
		public double getPrice() {
			return v / (double)w;
		}
		@Override
		public int compareTo(Obj o) {
			if(this.getPrice() == o.getPrice()) return 0;
			else if(this.getPrice() < o.getPrice()) return -1;
			else return 1;
		}
	}
}

乘船问题：

有n个人，第i个人重量为wi。每艘船的最大载重量均为C，且最多只能乘两个人。用最少的船装载所有人。默认最重的人等于船能承载的最大重量。

贪心策略：考虑最轻的人i，如果每个人都无法和他一起坐船（重量和超过C），则唯一的方案是每个人坐一艘
否则，他应该选择能和他一起坐船的人中最重的一个j

求需要船的数量

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
import java.util.Arrays;

public class 乘船问题 {

	public static void main(String[] args) {
		int[] w = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
		int n = w.length;
		int c = 10;
		Arrays.sort(w);
		int cnt = 0;
		int begin = 0;
		int end = w.length - 1;
		while(begin <= end) {
			if(w[begin] + w[end] > 10) {
				end--;
				cnt++;
			}else {
				begin++;
				end--;
				cnt++;
			}
		}
		System.out.println(cnt);
	}
}

程序运行结果：

1
6

贪心算法小结：

  • 最优子结构：对比dfs，不是进行各种可选支路的试探，而是当下就可以用某种策略确定选择，无需考虑未来（未来的情况下演变也影响不了当下的选择）
  • 只要一直这么选下去，就能得出最终的解，每一步都是的当（子问题）的最优解，结果是原问题的最优解，这叫做最优子结构。
  • 更书面的说法：如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。
  • 具备这类结构的问题，可以用局部最优解来推导全局最优解，可以认为是一种剪枝法，是对“dfs遍历法”的优化。
  • 贪心：由上一步的最优解推导下一步的最优解，而上一步之前的（历史）最优解则不作保留。
坚持原创技术分享，您的支持将鼓励我继续创作！