[集训Day4]贪心算法从入门到入土

贪心算法,是寻找最优解问题的常用方法,这种方法模式一般将求解过程分成若干个步骤,但每个步骤都应用贪心策略,选取当前状态下最好/最优的选择(局部最优解),并以此希望最后堆叠出的结果也是最好/最优的解。

贪心算法入门(Greedy algorithm)

解决贪心问题的基本步骤

  1. 将原问题分解为子问题
  2. 找出贪心策略
  3. 得到每一个子问题的最优解
  4. 将所有局部最优解的集合构成称为原问题的一个解

思路分析

贪心算法的根本    \implies策略的选择

贪心算法的根本在于贪心策略的选择,如果能找出正确的贪心策略的话,贪心问题也就迎刃而解。

贪心策略:即我们需要找到一种方法使得当前可以获得的收益最大。举个栗子:我们每个人都对未来有很多憧憬和计划。我们希望我们的人生都能得到最优解。但是由于我们无法预知之后几年几十年的事情发展,我们无法精准地计算出我们在每一个时间节点的完美选择。于是我们只好选择每一天,或者当前时间段我都做对自己最有帮助的事情。经过不断地积累最后得到最终结果,未必不是一种好的做法。

例题分析

P1090 合并果子

题目描述

在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过 n1n-1 次合并之后, 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 11 ,并且已知果子的种类 数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。

例如有 33种果子,数目依次为 112299。可以先将 1122 堆合并,新堆数目为 33 ,耗费体力为 33 。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为 1212 ,耗费体力为 1212 。所以多多总共耗费体力 =3+12=15=3+12=15 。可以证明 1515 为最小的体力耗费值。

输入格式

共两行。
第一行是一个整数 n(1n10000)n(1\leq n\leq 10000) ,表示果子的种类数。

第二行包含 nn 个整数,用空格分隔,第 ii 个整数 ai(1ai20000)a_i(1\leq a_i\leq 20000)是第 ii 种果子的数目。

输出格式

一个整数,也就是最小的体力耗费值。输入数据保证这个值小于 2312^{31}

说明/提示

对于3030%的数据,保证有n1000n \le 1000
对于5050%的数据,保证有n5000n \le 5000
对于全部的数据,保证有n10000n \le 10000

洛谷P1090

既然是贪心的思想:那么就首先要将问题分解成为子问题,然后着眼于子问题的最优解,最后将所有子问题的最优解汇总即可

nn堆的果子一定会经过n1n-1次合并,而每次消耗的体力之和为两堆果子的重量。其实很明显,我们要先搬重量小的那些堆,因为这样重的堆就不会被多次搬运而被算入被消耗地体力。

我们也就可以得出这道题最终要采用的贪心策略:每次取出两个最小的进行合并,合并完后再将新的堆存入,再进行重复操作。由于这里涉及到了排序,最优的方法就是用STL里的堆。

AC代码如下:

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
#include <bits/stdc++.h>//建议不要使用万能头QwQ
using namespace std;

priority_queue<int,vector<int>,greater<int> > qwq;
int n;
int main(){
cin>>n;
int x,a,b,ans = 0;
for(int i = 0;i<n;i++){
cin>>x;
qwq.push(x);
}

while(qwq.size()>=2){
a = qwq.top();
qwq.pop();
b = qwq.top();
qwq.pop();
ans += (a+b);
qwq.push(a+b);
}

cout<<ans<<endl;
return 0;
}

P1253 线性存储问题

洛谷P1253

这道题的贪心策略也很明显,我们可以把Li×FiL_i\times F_i看做查询一个数据的时间,那么我们就可以将时间长的放在前面。

由于要储存三个数据(L1L_1FiF_i、编号ii),所以我这里选择使用结构体+sort+自定义函数来解决排序问题

AC代码如下:

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

struct qwq{
int l,f,i;
}orz[10002];

bool cmp(qwq a,qwq b){
return (a.l*a.f > b.l*b.f);
}

int main(){
int n;
cin>>n;
for(int j = 1;j <= n;j++){
cin>>orz[j].l>>orz[j].f;
orz[j].i = j;
}

sort(orz+1,orz+1+n,cmp);

for(int j = 1;j <= n;j++){
cout<<orz[j].i<<" ";
}

return 0;
}

存在的问题和难点

  1. 证明困难,大部分的贪心算法难以证明
  2. 大部分情况下其实并不是最优解
  3. 贪心问题之间的跨越度比较大
文章作者: Tim
文章链接: http://itstim.xyz/%E9%9B%86%E8%AE%ADDay4-%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E4%BB%8E%E5%85%A5%E9%97%A8%E5%88%B0%E5%85%A5%E5%9C%9F/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Tim's Blog
支付宝恰饭打赏
微信恰饭打赏