Tragedy of Greedy Algorithm

发表于   |   分类于   |  

Background

It is said that, long long time ago, the poor rabbit experienced the biggest blow in her life - lost a race to the tortoise, depressed in her heart and swearing to avenge. Since then, she hid in a Hangzhou Xiasha, an agricultural park, practicing industriously. Finally she mastered the skills- running without rest and running at constant velocity (VR M/s). So, she has been trying to find a chance to teach a lesson to the tortoise.

Recently when HDU held the 50 anniversary, the major social celebrities it in Xiasha, the rabbit would also take this opportunity to challenge the tortoise. While the tortoise knows that winning is rarely impossible, but under the pressure from public, he had no chance but to accept the challenge.

The game is based on a straight road ( L meters long ), and the rules are very simple- who first arrived at the end who win the game.

Since his last win, having become a popular tortoise, being called the “Liu Xiang of the animal kingdom” by a series magazines, he has made big money. In order to win the rabbit, tortoise spent most of his savings buying the most advanced weapon – “ Xiaofeige “ electric vehicles. The vehicle can reach to the spend of VT1 M/s but limited by small battery capacity. When it is full of electricity it can travel a distance of C meters, then can only drive by foot at the speed of VT2 M/s. More over, the tortoise built a lot of (N) power stations on the runway, for charging his electric vehicle. Additionally, charging takes T seconds for each time. Of course, the tortoise can choose to charge or not to charge when past a station.

The race is about to start, and the rabbit and the tortoise, with his electronic vehicles full of electricity, stand on the starting line. Your task is to write a program to find the best schedule for the tortoise. Can the tortoise win the rabbita at constant speed?

Input && Output

Input

1st Line：L //the length of road
2st Line：N，C，T //number of station, the max distance the vehicle can reach with full electricity, the time charging takes each time
3st Line：VR，VT1，VT2 //the speed of rabbit, tortoise’s vehicle with electricity, tortoise’s vehicle without electricity
4st Line：p1,p2…pn //the distance from the starting line to each station

Output

If the tortoise has chance to win the rabbit then print “What a pity rabbit!”
Else print “Good job,rabbit!”

Sample

Input

这里写图片描述

Output

Good job,rabbit!
What a pity rabbit!
What a pity rabbit!

Greedy

The tragedy of greedy algorithm is that the result of single course schedule task is not global optimal. The greedy algorithm answer for the three cases are：

Good job,rabbit!
What a pity rabbit!
Good job,rabbit!

When you use greedy algorithm you will get the same answers as first and second case, but the opposite answer against the third case.In three case, using greedy algorithm, the tortoise will stop at the second station without a stop at the first one and the tortoise will spend 27s, more the time rabbit spend. But the best schedule spend 23s when the tortoise stop at the first station, not the second one.That’s why you will get the WA answer for the third case.

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
//Title：WA code
//Author：Call偶围城
#include <stdio.h>
#define MAX 100
int main() {
	int L;
	int N, C, T;
	int VR, VT1, VT2;
	double TR, TT, TT1, TT2;
	int dis[MAX], a, b;
	int remain, r1, r2;
	int i;
	while (scanf("%d%d%d%d%d%d%d", &L, &N, &C, &T, &VR, &VT1, &VT2) != EOF) {
		a = b = 0;
		for (i = 0;i < N;i++) {
			scanf("%d", &b);
			dis[i] = b - a;
			a = b;
		}
		dis[i] = L - a;
		TR = L*1.0/VR;
		
		if (dis[0] < C) {
			TT = dis[0]*1.0/VT1;
			remain = C - dis[0];
		}
		else {
			TT = C*1.0/VT1 + (dis[0]-C)*1.0/VT2;
			remain = 0;
		}
		for (i = 1;i <= N;i++) {
			TT1 = T;
			r1 = C;
			r2 = remain;
			if (dis[i] < C) {
				TT1 = TT1 + dis[i]*1.0/VT1;
				r1 = C - dis[i];
			}
			else {
				TT1 = TT1 + C*1.0/VT1 + (dis[i]-C)*1.0/VT2;
				r1 = 0;
			}
			if (dis[i] < remain) {
				TT2 = dis[i]*1.0/VT1;
				r2 = remain - dis[i];
			}
			else {
				TT2 = remain*1.0/VT1 + (dis[i]-remain)*1.0/VT2;
				r2 = 0;
			}
			if (TT1 < TT2) {
				TT += TT1;
				remain = r1;
			}
			else {
				TT += TT2;
				remain = r2;
			}
			if (TT > TR)
				break;
		}
		if (TT < TR)
			printf("What a pity rabbit!\n");
		else
			printf("Good job,rabbit!\n");
	}
	return 0;
}

Dynamic Programming

Recursion Formulae：dp[i] = min ( dp[j] + Tj ), 0 <= j smaller than i
You can see the problem as 0/1 knapsack problem in which the volume of bag is infinit and the value of each item is relative to the previous items. The aim of the problem is to find the lightest weight when you stuff all the items into the bag.

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
//Title：AC code
//Author：Call偶围城
#include <stdio.h>
#define MAX 105
#define INF 1000000
int main() {
	int L;
	int N, C, T;
	int VR, VT1, VT2;
	int dis[MAX], map[MAX][MAX];
	double dp[MAX];
	int i, j;
	double t;
	while (scanf("%d%d%d%d%d%d%d", &L, &N, &C, &T, &VR, &VT1, &VT2) != EOF) {
		dis[0] = 0;
		for (i = 1;i <= N;i++) {
			scanf("%d", &dis[i]);
		}
		dis[i] = L;
		for (i = 0;i <= N+1;i++) {
			for (j = i+1;j <= N+1 ;j++) {
				map[i][j] = dis[j] - dis[i];
			}
		}
		for (i = 1;i <= N+1;i++) {
			dp[0] = 0.0;
			dp[i] = INF*1.0;
			for (j = 0;j < i;j++) {
				if (map[j][i] < C)
					t = map[j][i]*1.0/VT1;
				else
					t = C*1.0/VT1 + (map[j][i]-C)*1.0/VT2;
				if (j != 0)
					t += T;
				if (dp[i] > dp[j] + t)
					dp[i] = dp[j] + t;
			}
		}
		printf(dp[N+1]<L*1.0/VR ? "What a pity rabbit!\n":"Good job,rabbit!\n");
	}
	return 0;
}

Also, you can see the time of rabbit as the volume of the bag and to find if there is any method to stuff all the items into the bag with limited volume.