|
贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。举个简单的例子，即找零，例如需要给顾客85元现金，为使货币数量最少，应该选不超过85的面钞50元，然后20元，接着10元，最后5元，这就是最简单的贪心算法实例。
??此为自顶而下，与之对应的动态规划则是自底而上。
??方法：1创建数学模型来描述问题。
??2把求解的问题分成若干个子问题。
??3对每一子问题求解，得到子问题的局部最优解。
??4把子问题的解局部最优解合成原来解问题的一个解。
Greedy(C){
S={};
while(not solve(S)){
x=select(C);
if feasible(S,x){
S=S+{x};
C=C-{x};
}
}
return S;
}
??经典题目描述1：[FatMouse’s Trade]:fatmouse有m puonds猫粮，想要和猫换取食物，猫看管着n间仓库，没见仓库里有j[i]pounds食物，需要用f[i]pounds猫粮才能换取，没见仓库的食物不用全部换取， j[i] * a% = f[i] * a%, 问fatmouse最多可以换取多少食物。
??分析：很经典的贪心演算法，利用结构体，根据换取利率排序，然后将阵列跑一遍。举个简单的例子，例如m=5,n=3，当输入7 2，4 3，5 2；将输出13.333.原因：先挑选不超过m的组，然后进行挑选最多的，选7，然后5，最后m剩余1个，此时进入第二组，则4/3*1=1.333，总共为13.33，所以该算法将每一组的J[I]/F[I]进行排序，每一个组都有一个性价比。
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
struct inp{
double x,y;
double c;
}node[1005];
bool cmp(inp a,inp b){
return a.c>b.c;
}
int main(){
int i,n,m;
double j;
while(cin>>m>>n&&n!=-1&&m!=-1){
for(i=0;i<n;i++){
cin>>node[i].x>>node[i].y;
node[i].c=node[i].x/node[i].y;
}
sort(node,node+n,cmp);
j=0;
for(i=0;i<n;i++) {
if (node[i].y <= m) {
j += node[i].x;
m -= node[i].y;
} else {
j += m * node[i].c;
break;
}
}
printf("%.3f",j);
}
return 0;
}
??经典题目2：[今年暑假不AC hdu2037]“今年暑假不AC？”“是的。”“那你干什么呢？”“看世界杯呀，笨蛋！”“@#$%^&*%…”确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）
Input
??输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。
Output
??对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。
??分析：此类题型属于时间序列问题，例如下表
| 事件编号 | 发生时刻 | 结束时刻 |
|---|
| 0 | 1 | 3 | | 1 | 3 | 4 | | 2 | 0 | 7 | | 3 | 3 | 8 | | 4 | 2 | 9 | | ... | ... | ... |
??Begin[i]和End[i]表示结束，其实就是要寻找最长序列满足Begin[i]<End[j]<…Begin[m]<End[n]。所以针对上述问题只需要对发生结束时刻排序即可，属于常规的贪心算法。
#include <iostream>
#include <algorithm>
using namespace std;
struct inp{
int Begin;
int End;
}node[100];
bool cmp(inp a,inp b){
return a.End<b.End;
}
int main(){
int n,i,count,j;
while(cin>>n&&n){
count=1,j=0;
for(i=0;i<n;i++){
cin>>node[i].Begin>>node[i].End;
}
sort(node,node+n,cmp);
for(i=1;i<n;i++){
if(node[j].End<=node[i].Begin){
count++;
j=i;
}
}
cout<<count<<endl;
}
return 0;
}
??经典题目3：有一堆木棍。每根棍子的长度和重量是预先知道的。木棒要由木工机器一一加工。机器准备加工棒材需要一些时间，称为设置时间。设置时间与机器中的清洁操作和更换工具和形状有关。木工机的设置时间如下：(a) 第一根木棒的设置时间为 1 分钟。(b) 刚加工完长度为 l 和重量为 w 的木棒后，如果 l<=l’ 和 w<=w’，机器将不需要为长度为 l’ 和重量为 w’ 的木棒准备时间。否则，将需要 1 分钟进行设置。
?? 您将找到处理给定的 n 根木棍的最短设置时间。例如，如果您有五根木棍，其长度和重量对分别为 (4,9)、(5,2)、(2,1) , (3,5), 和 (1,4)，那么最小设置时间应该是 2 分钟，因为有一系列对 (1,4), (3,5), (4,9), (2, 1)、(5,2)。
输入
??输入由 T 个测试用例组成。测试用例的数量 (T) 在输入文件的第一行中给出。每个测试用例由两行组成：第一行有一个整数n，1<=n<=5000，表示测试用例中木棒的数量，第二行包含n个2个正整数l1,w1,l2,w2 , …,ln, wn, 每个幅度最大为 10000 ，其中 li 和 wi 分别是第 i 根木棒的长度和重量。2n 个整数由一个或多个空格分隔。
输出
??输出应包含以分钟为单位的最小设置时间，每行一个。
分析：这是经典的区域覆盖问题。
#include <iostream>
#include <algorithm>
using namespace std;
struct lip{
int l,w;
}node[5000];
bool cmp(lip a,lip b){
return a.l<b.l||(a.l==b.l&&a.w<b.w);
}
int main(){
int n,i,count,t;
while(cin>>t){
while(t--){
while(cin>>n){
for(i=0;i<n;i++){
cin>>node[i].l>>node[i].w;
}
sort(node,node+n,cmp);
count=1;
for(i=1;i<n-1;i++){
if(node[i].l>node[i+1].l||node[i].w>node[i+1].w){
count++;
}
}
cout<<count;
}
}
}
return 0;
}
??以上是部分练习，对于贪心算法需要多训练，其实通过这几题很明显看出地看出贪心算法的优势，要对预处理的数据进行排序，当然在此之前要建立结构体来存储记录多组数据，便于比较性价比。不过，贪心算法终究是有不足的，在使用此算法前，需能证明（或显然）可以使用，这种算法类似于在剩余条件中寻找最优的数据，并且即使后面不满足不能返回处理（区别与分而治之、动态规划）。
??后续还将有一些关于贪心算法的练习，当然还有更多的算法专项在进行中。
|