一文读懂贪心算法

概念及使用

贪心算法或贪心思想采用贪心的策略,保证每次操作都是局部最优,从而使最后得到的结果是全局最优

通常不使用回溯

适用条件:
1.问题具有最优子结构性质:问题的最优解可以通过子问题的最优解推导得到。
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
#include <iostream>
#include <algorithm>

using namespace std;

int findContentChildren(int g[], int gSize, int s[], int sSize) {
// 对孩子的饥饿度和饼干的大小进行排序
sort(g, g + gSize);
sort(s, s + sSize);

int childIndex = 0; // 孩子的索引
int cookieIndex = 0; // 饼干的索引

// 遍历饥饿度和饼干大小,尝试满足孩子
while (childIndex < gSize && cookieIndex < sSize) {
if (s[cookieIndex] >= g[childIndex]) {
// 当前饼干可以满足当前孩子的饥饿度
childIndex++;
}
// 无论是否满足孩子,饼干索引都需要移动
cookieIndex++;
}

return childIndex; // 最终满足的孩子数量
}

int main() {
int g[] = {1, 2}; // 孩子的饥饿度
int s[] = {1, 2, 3}; // 饼干的大小
int gSize = sizeof(g) / sizeof(g[0]);
int sSize = sizeof(s) / sizeof(s[0]);

int result = findContentChildren(g, gSize, s, sSize);
cout << "最多有" << result << "个孩子可以吃饱。" << endl;

return 0;
}

【深基12.例1】部分背包问题

链接:https://www.luogu.com.cn/problem/P2240

题目描述

阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 $N(N \le 100)$ 堆金币,第 $i$ 堆金币的总重量和总价值分别是 $m_i,v_i(1\le m_i,v_i \le 100)$。阿里巴巴有一个承重量为 $T(T \le 1000)$ 的背包,但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割,分割完的金币重量价值比(也就是单位价格)不变。请问阿里巴巴最多可以拿走多少价值的金币?

输入格式

第一行两个整数 $N,T$。

接下来 $N$ 行,每行两个整数 $m_i,v_i$。

输出格式

一个实数表示答案,输出两位小数

样例 #1

样例输入 #1
1
2
3
4
5
4 50
10 60
20 100
30 120
15 45
样例输出 #1
1
240.00

解题思路:使用贪心算法那首先想到金币按照价值的高低排序,先装价值高的。又因为是可以分割的,可以知道应该以价格的单位价值为分类标准,所以在获取输入时候就可以把单位价值计算出来。
又因为金币的性质很多,所以用到结构体,排序用sort函数,定义compare。
那就循环遍历数组,依次累加价值,直到价值超过了背包。超过背包也不能直接return,要看是不是有剩余的价值(也就是拆开的金子)
最后就可以直接输出了 代码如下:

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
#include <iostream>
#include <algorithm>
#include <iomanip>

using namespace std;

struct GoldPile {
int weight;
int value;
double unit_value;
};

bool compare(GoldPile a, GoldPile b) {
return a.unit_value > b.unit_value;
}

int main() {
int N, T;
cin >> N >> T;

GoldPile gold[N];

for (int i = 0; i < N; i++) {
cin >> gold[i].weight >> gold[i].value;
gold[i].unit_value = (double)gold[i].value / gold[i].weight;
}

sort(gold, gold + N, compare);

double max_value = 0.0;
int current_weight = 0;

for (int i = 0; i < N && current_weight < T; i++) {
if (current_weight + gold[i].weight <= T) {
current_weight += gold[i].weight;
max_value += gold[i].value;
} else {
int remaining_weight = T - current_weight;
max_value += remaining_weight * gold[i].unit_value;
break;
}
}

cout << fixed << setprecision(2) << max_value << endl;

return 0;
}

凌乱的yyy / 线段覆盖

links: https://www.luogu.com.cn/problem/P1803

题目背景

快 noip 了,yyy 很紧张!

题目描述

现在各大 oj 上有 $n$ 个比赛,每个比赛的开始、结束的时间点是知道的。

yyy 认为,参加越多的比赛,noip 就能考的越好(假的)。

所以,他想知道他最多能参加几个比赛。

由于 yyy 是蒟蒻,如果要参加一个比赛必须善始善终,而且不能同时参加 $2$ 个及以上的比赛。

输入格式

第一行是一个整数 $n$,接下来 $n$ 行每行是 $2$ 个整数 $a_{i},b_{i}\ (a_{i}<b_{i})$,表示比赛开始、结束的时间。

输出格式

一个整数最多参加的比赛数目。

样例 #1

样例输入 #1
1
2
3
4
3
0 2
2 4
1 3
样例输出 #1
1
2
提示
  • 对于 $20%$ 的数据,$n \le 10$;
  • 对于 $50%$ 的数据,$n \le 10^3$;
  • 对于 $70%$ 的数据,$n \le 10^{5}$;
  • 对于 $100%$ 的数据,$1\le n \le 10^{6}$,$0 \le a_{i} < b_{i} \le 10^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
#include <iostream>
#include <algorithm>

using namespace std;

// 比赛结构体
struct Event {
int start;
int end;
};

// 比较函数,用于按结束时间排序
bool compare(Event a, Event b) {
return a.end < b.end;
}

int main() {
int n;
cin >> n;

Event events[n];

// 输入比赛的开始和结束时间
for (int i = 0; i < n; ++i) {
cin >> events[i].start >> events[i].end;
}

// 按结束时间排序
sort(events, events + n, compare);

int count = 0; // 记录最多能参加的比赛数
int last_end_time = -1; // 记录上一个选中比赛的结束时间

// 贪心选择不重叠的比赛
for (int i = 0; i < n; ++i) {
if (events[i].start >= last_end_time) {
// 选择当前比赛
count++;
last_end_time = events[i].end;
}
}

cout << count << endl;

return 0;
}