内容导引:
贪心算法的基本思想
贪心算法的基本思路
贪心算法的进行过程
基本题型与例题解析
基本思想:
基本要素:
基本思路:
从问题的初始状态开始,往最终状态前进,每次都选择当前最好的选择。当到达最终状态时停止;如果不能再作出选择,又未到达最终状态,那么这个问题不能或利用贪心思想不能到达最终状态,停止。
执行过程:
用一个背包问题来解释:
有一个背包,其容量M一定。物品有若干个,要求尽可能让装入背包中的物品的总价值最大,但是不能超过总容量。
那么贪心思路有一下三个:
思路分析:
如何解决背包问题:
种类一:一般贪心(交换)问题
HDU 1009 Fat Mouse’ Trade
Fat Mouse 准备了M磅猫粮,准备和看守存放了他最喜欢的食物-咖啡豆的房间的猫进行交易。猫看守着N间房间,第i间房间存放了J[i]磅咖啡豆,交换所有咖啡豆需要F[i]磅的猫粮,FM不必交换整个房间的咖啡豆,也就是说,他可以用(F[i]*a)%磅的猫粮交换得到(J[i]*a)%磅咖啡豆。现在他请你帮忙,帮他交换到最多数量的咖啡豆。
数据分析如下:
分析:
题目描述似乎和之前的背包问题很相像,但是题目多了一个可以用一部分猫粮换取一部分咖啡豆的条件。如果那个背包问题也加入这样的条件,那就可以保证背包能够装满,这样就可以用贪心去解决。
那么这个问题,可以选择之前的思路三,选择放前单位猫粮换取的咖啡豆最多的房间进行交易,直到猫粮用完。
得出解决方案后,先验证一下第一组数据,三个房间分别是3.5;1.333;2.5,先换房间1和3的,都可以全部换到。剩下房间2不能换到所有的咖啡豆,因为猫粮剩余1,只能换到1/3,那么结果就是7+5+4*(1/3)=13.333,答案正确。
题解传送门:http://www.ocrosoft.com/?p=200
类型二:时间安排问题(区间覆盖)
HDU 2037 今年暑假不AC
小A列出了一些想看的电视节目,上面表明了电视节目的开始和结束时间,但是一些电视节目是冲突的,现在他想尽可能多地而且完整地看电视节目,请你帮忙。
数据分析如下:
分析:
时间安排问题,用贪心总能得到整体最优解,用数学归纳法可以证明,证明不重要,从略。
可以先对所有的节目以结束时间从早到晚进行排序,结束时间相同的时候,按照开始时间从早到晚排序。
然后看第一个节目,它的开始时间最早,结束时间最早,那么这个节目是一定要看的。然后后面的节目都对比前一个看的节目的结束时间,如果此时还在看上一个节目,那么继续看前一个节目,放弃这一个节目。直到分析完所有节目。
题解传送门:http://www.ocrosoft.com/?p=204
类型三:线段覆盖问题(区间覆盖)
这种类型和类型二非常类似,要求计算一些线段覆盖的总长度,只需要对类型二稍加修改,排序的时候先按照开始时间排序,再按结束时间排序。总长先记为线段1的全长,然后线段2和线段1比较,如果线段2不与线段1重复,总长就加上线段2的全长;如果线段2结束点在线段1结束点前,那么线段2长度不计;如果线段2与1重复且结束点不在线段1内部,则总长加上线段1结束点到线段2结束点的长度。
如下数据:答案为13。
#include <set> #include <map> #include <list> #include <cmath> #include <stack> #include <queue> #include <ctime> #include <string> #include <cstdio> #include <vector> #include <cctype> #include <climits> #include <sstream> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #define ms(a) memset(a,0,sizeof(a)) #define INF INT_MAX #define MAXN 500+10 using namespace std; struct Node { int s,f; bool operator<(const Node t)const { if(s==t.s)return f<t.f; else return s<t.s; } } node[15]; int n; int main() { while(cin>>n&&n) { for(int i=0; i<n; i++) scanf("%d%d",&node[i].s,&node[i].f); int ans=node[0].f-node[0].s; for(int i=1,j=0;i<n;i++) { if(node[i].s>node[j].f)//如果这条线段跟前面的没有重叠 { ans+=node[i].f-node[i].s;//计算这条线段的全场 j=i; } else { if(node[i].f<=node[j].f)continue;//如果这条线段结束点在上一条线段的内部,这条线段不计长度。 //可能会考虑如果这条线段开始比上一条长的情况,但是排序的时候已经排除了这种情况。 ans+=node[i].f-node[j].f; j=i; } } printf("%d\n",ans); } return 0; }
类型四:数字组合问题
分析:
不能拆分的情况,有两种,1是只有一位,2是去掉0后只有一位,在判断的时候这两种可以归为一种。例:1和10000。
能拆分的情况,一定是拆分成n-1位和1位的两个数,这个1位的数,一定取除了0以外的最小的数。n-1位的数就像例1一样,从大到小排好。题目要求输出和,进行一下大数加法就可以了。
贪心算法到这里就结束了,如果有错误请指正,谢谢。