贪心算法

引导问题:硕鼠问题

FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.
The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.

Input
The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1’s. All integers are not greater than 1000.

Output
For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.

Sample Input
5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1

Sample Output
13.333
31.500

初始“贪心算法“

  • 在对问题求解时,总是作出在当前来看最好选择。
  • 也就是说,不从整体上加以考虑,所作出的仅仅是在某种意义上的局部最优解(是否是全局最优解需要证明)。

例1

经典贪心-时间序列

已知N个事件的发生时刻和结束时刻。一些在时间上没有重叠的事件序列,如事件{2,8,10}。事件序列包含的时间数目,称为该事件的序列长度

。请编程找出一个最长的事件序列

事件编号|0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10 |11

发生时刻|1 |3 |0 |3 |2 |5 |6 |4 |10|8 |15 |15

结束时刻|3 |4 |7 |8 |9 |10|12|14|15|18|19|20

分析

编号2 8 10 的事时间没有交叉部分,这种不重叠的事件构成事件序列

想法

  • 耗时最短
  • 从最早开始的节目开始找
  • 找最早结束的

反证法证明贪心思路正确性:

​ 假设所有的最长事件序列都不包含最早结束,任选一个最长事件序列,因为不包括最早结束的事件,所以将第一件事换为最早结束事件,结果并不冲突

例2

ROOM1 ROOM3 ROOM5 … ROOM397 ROOM399

​ 走廊

ROOM2 ROOM4 ROOM6 … ROOM398 ROOM400

输入n,n为接下来输入的数据组数,接着输入n组数据,

每组先输入m,接下来输入m行A B,表示从A号房间向B号房间搬桌子,走廊一次只能走一张桌子(不能发生交叉),不论远近一次耗时10分钟 。

Sample Input:

3

4

10 20

30 40

50 60

70 80

2

1 3

2 200

3

10 100

20 80

30 50

Sample Output:

10

20

30

例3

已知一个长度不超过240位的正整数n(其中不含有数字0),去掉任意s(s小于n的长度)个数字后,将剩下的数字按原来的左右次序组成一个新的正整数。

给定n和s,请编程输出最小的新正整数。

Sample Input:

178543 4

Sample Output:

13

例4

未名湖附近共有n 个大小湖泊L1, L2, …, Ln(其中包括未名湖),每个湖泊Li 里住着一只青蛙Fi(1≤i≤n)。如果湖泊Li 和Lj 之间有水路相连,则青蛙Fi 和Fj 互称为邻居。现在已知每只青蛙的邻居数目x1, x2, …, xn,请你给出每两个湖泊之间的相连关系。

输入n,再输入n组数据,m,s1,s2,…,sm,m代表湖泊数量

输出Yes或No

Sample Input:

3

7

4 3 1 5 4 2 1

6

4 3 1 4 2 0

6

2 3 1 1 2 1

​ Sample Output:

Yes

No

Yes

两个概念:

1.度序列:若把所有顶点的度数排成一个序列s,则称s为图g的度序列。

2.序列是可图的:一个非负整数组成的有限序列如果是某个无向图的度序列,则称该序列是可图的。

Havel-Hakimi定理

由非负整数组成的非增序列S:d1,d2,…,dn(n>=2,d1=1)是可图的,当且仅当序列S1:d2-1,d3-1,…,dd1+1-1,dd1+2,…,dn是可图的。

其中,序列S1中有n-1个非负整数,S序列中d1后的前d1个度数(即d2~dd1+1)减1后构成S1中的前d~ 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
#include <bits/stdc++.h>
using namespace std;

struct Event
{
int ID;
int startTime;
int endTime;
};

bool cmp(struct Event a, struct Event b)
{
return a.endTime < b.endTime;
}

int main()
{
vector<int> ans;
Event events[12] = {
{0, 1, 3},
{1, 3, 4},
{2, 0, 7},
{3, 3, 8},
{4, 2, 9},
{5, 5, 10},
{6, 6, 12},
{7, 4, 14},
{8, 10, 15},
{9, 8, 18},
{10, 15, 19},
{11, 15, 20}};
//本题已排好序
sort(events, events + 12, cmp);
ans.push_back(events[0].ID);
int last = 0;
for (int i = 1; i < 12; i++)
{
if (events[i].startTime >= events[last].endTime)
{
last = i;
ans.push_back(i);
}
}
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << " ";
return 0;
}

例2

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
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t,i,j,N,P[200];
int s,d,temp,k,MAX;
cin>>t;
for(int i=0;i<t;i++)
{
for(j=0;j<200;j++)
P[j]=0;
cin>>N;
for(j=0;j<N;j++)
{
cin>>s>>d;
s=(s-1)/2;
d=(d-1)/2;
if(s>d)
{
temp=s;
s=d;
d=temp;
}
for(k=s;k<=d;k++)
{
P[k]++;
}
}
MAX=-1;
for(j=0;j<200;j++)
{
if(P[j]>MAX)
{
MAX=P[j];
}
}
cout<<MAX*10<<endl;
}
return 0;
}

例3

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
#include <iostream>
#include <string>
using namespace std;
//从数字字符串s中删除n个字符,使结果最小
string deleteKNumbers(string &str, int k)
{
bool isSequence;
for (int i = k; i > 0; i--)
{
isSequence = true;
for (auto start = str.begin(); start < str.end() - 1; ++start)
{
if (*start > *(start + 1)) // 每次删除第一个比下一个数字大的数
{
str.erase(start);
isSequence = false;
break;
}
}
if (isSequence) //如果所有数字递增,则删除最后几个数字直接返回
{
str.erase(str.end() - i, str.end());
break;
}
}
return str;
}

int main()
{
string s;
int n;
while (cin>>s>>n)
cout << deleteKNumbers(s, n) << endl;
return 0;
}

例4

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
#include <bits/stdc++.h>
using namespace std;

int main()
{
int n;
cin >> n;
while (n--)
{
vector<int> neighbors;
int m;
cin >> m;
for (int i = 0; i < m; i++)
{
int temp;
cin >> temp;
neighbors.push_back(temp);
}
bool isTrue = true; //是否成图
while (neighbors.size() != 0)
{
sort(neighbors.begin(), neighbors.end());
reverse(neighbors.begin(), neighbors.end());
int temp = neighbors[0]; //邻居最多的青蛙有多少邻居
if (temp ** 0)
break;
auto it = neighbors.begin();
neighbors.erase(it);
for (int i = 0; i < temp; i++)
{
neighbors[i]--;
}
}
for (int i = 0; i < neighbors.size(); i++)
{
if (neighbors[i] != 0) //全为零则成图
isTrue = false;
}
if (isTrue)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}