一文读懂贪心算法
概念及使用
贪心算法或贪心思想采用贪心的策略,保证每次操作都是局部最优,从而使最后得到的结果是全局最优的
通常不使用回溯
适用条件:
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
解题思路:使用贪心算法那首先想到金币按照价值的高低排序,先装价值高的。又因为是可以分割的,可以知道应该以价格的单位价值为分类标准,所以在获取输入时候就可以把单位价值计算出来。
又因为金币的性质很多,所以用到结构体,排序用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
提示
- 对于 $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; }
|
评论
Gitalking ...