网站建设php文件放哪里,网站建设哪家go好,企业seo哪些公司好,漯河网上商城网站建设1. 前言
贪心算法是一种常见算法。是以人性之念的算法#xff0c;面对众多选择时#xff0c;总是趋利而行。
因贪心算法以眼前利益为先#xff0c;故总能保证当前的选择是最好的#xff0c;但无法时时保证最终的选择是最好的。当然#xff0c;在局部利益最大化的同时面对众多选择时总是趋利而行。
因贪心算法以眼前利益为先故总能保证当前的选择是最好的但无法时时保证最终的选择是最好的。当然在局部利益最大化的同时也可能会带来最终利益的最大化。
假如在你面前有 3 个盘子分别放了很多苹果、橙子、梨子。
现以贪心之名从 3 个盘子里分别拿出其中最重的那个则能求解出不同品种间最重水果的最大重量之和。这时3 个盘子可认为是 3 个子问题局部问题。
贪心算法会有一个排序过程。当看到盘子里的水果时潜意识中你就在给它们排序。有时因可排序的属性较多必然导致使用贪心算法求解问题时贪心策略可能会有多种。
比如说选择水果你可以选择每盘里最大的、最重的、最成熟的……具体应用那个策略要根据求解的问题要求而定。贪心策略不同导致的结论也会不一样。
本文将通过几个案例深入探讨贪心算法的贪心策略。
2. 活动安排问题
问题描述
有n个活动a1,a2,…,an……需要在同一天使用同一个教室且教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一个活动被选择后另一个活动则需等待前一个活动结束后方可进入教室。请问如何安排这些活动才能使得尽量多的活动能不冲突的举行。
分析问题
教室同一时间点只能安排一个活动如果活动与活动之间存在时间交集重叠则这两个活动肯定是不能在同一天安排。
使用 S表示活动的开始时间f表示活动的结束时间。则可使用 [si,fi]表示活动一[sj,fj]表示活动二。
如果存在sisjfifj则称这 2 个活动不相容不相容的活动不能在一天内同时出现。如下图所示。 只有当活动二的开始时间等于或晚于上活动一的结束时间时方可以在同一天出现。如下图所示。也即sjfi。此时称这 2 个活动是相容。 此问题中活动的属性有
活动的开始时间。活动的结束时间。活动的时长。
那么在使用贪心算法时贪心的策略应该如何定夺
2.1 贪心策略
2.1.1 策略一
最直接的想法是每次安排活动时长最短的活动必然可保证一天内容纳的活动数最多。
逻辑层面上讲先以活动时长递增排序然后依次选择。
但是忽视了一个问题每一个活动都有固定的开始时间和结束时间。
如下图所示因活动一所需时长最短先选择。又因活动二所需时长次短选择活动二。因两个活动时间间隔较长采用此策略会导致教室出现空闲时间。 针对此问题贪心算法的出发点应该是保证每一时刻教室的最大利用率才有可能容纳最多活动。
显然受限于活动固定时间限制此策略不可行。
2.1.2 策略二
能否每次选择活动时长最长的活动。提出这个策略时就不是很自信的。分析问题吗就不论正确只论角度。
此策略和策略一相悖论。题目要求尽可能安排活动的数量如果某活动的时长很长一个活动就占据了大部分时间显然此种策略是无法实现题目要求的。
如下图选择活动一后再选择活动三。一天仅能安排 2 次活动。根据图示根据每个活动的开始、结束时间一天之内至少可以安排 3 个活动。 2.1.3 策略三
每次选择最早开始的活动。
先选择最早开始等活动结束后再选择相容且次开始的。这个策略和策略二会有同样的问题。如果最早开始的活动时长较长必然会导致大部分活动插入不进去。
2.1.4 策略四
还是回到策略一上面来以时长最短的活动为优先理论上是没有错的但是不能简单的仅以时长作为排序依据。
可以以活动结束时间为依据。活动结束的越早活动时长相对而言是较短的。因同时安排的活动需要有相容性所以再选择时可选择开始时间等于或晚于前一个活动结束时间的活动这也是与策略一不同之处并不是简单的选择相容且绝对时长短的活动。
在活动时长较短情况又能保证教室的使用时间一直连续的则必然可以安排的活动最多。如下图所示
选择最早结束的活动。开始时间与上一次结束时间相容的活动。如此反复。且保证活动的相容同时保持了时间上的连续性。 2.2 编码实现
#include iostream
#include algorithm
#define MAX 5
using namespace std;
/*
*描述活动的结构体
*/
struct Activity {//活动开始时间int startTime;//活动结束时间int endTime;//是否选择bool isSelfalse;void desc() {coutthis-startTime-this-endTimeendl;}
};
//所有活动
Activity acts[MAX];
//初始化活动
void initActivities() {for(int i0; iMAX; i) {cout输入活动的开始时间-结束时间endl;cinacts[i].startTimeacts[i].endTime;}
}
/*
*比较函数
*/
bool cmp(const Activity act0, const Activity act1) {return act0.endTimeact1.endTime;
}
/*
*活动安排
*/
int getMaxPlan() {//计数器int count1;//当前选择的活动int currentSel0;acts[currentSel].isSeltrue;for(int i1; iMAX; i) {if(acts[i].startTimeacts[currentSel].endTime ) {count;currentSeli;acts[i].isSeltrue;}}return count;
}
/*
*输出活动
*/
void showActivities() {for(int i0; iMAX; i) {if(acts[i].isSeltrue)acts[i].desc();}
}
/*
*测试
*/
int main() {initActivities();//排序使用 STL 算法中的 sortsort(acts,actsMAX,cmp);getMaxPlan();showActivities();return 0;
}输出结果 3. 调度问题
3.1 多机调度
问题描述
n个作业组成的作业集可由m台相同机器加工处理。要求使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。作业不能拆分成更小的子作业。
分析问题
此问题是可以使用贪心算法的可以把每一个作业当成一个子问题看待。
当nm时可满足每一个作业同时有一台机器为之服务。最终时间由最长作业时间决定。当nm时则作业之间需要轮流使用机器 这时有要考虑贪心策略问题。
本问题和上题差异之处不在意作业什么时候完成所以作业不存在开始时间和结束时间每个作业仅有一个作业时长属性。所以贪心策略也就只有 2 个选择
按作业时长从小到大轮流使用机器。
如果是求解在规定的时间之内能完成的作业数量最多则可以使用此策略。
而本题是求解最终最短时间此策略就不行。在几个作业同时工作时**最终完成的的时长是由最长时长的作业决定的。**这是显然易见的道理。一行人行走总是被行动被慢的人拖累。
如果把最长时长的作业排在最后则其等待时间加上自己的作业时长必然会导致最终总时长不是最优解。
按作业时长从大到小轮流使用机器。
先安排时长较长的作业最理想状态可以保证在它工作时其它时长较小的作业在它的周期内完成。 3.2 编码实现
#include iostream
#include algorithm
#include vector
#include cstring
using namespace std;//每个作业的工作时长
int* workTimes;
//机器数及状态
int* machines;/*
*初始化作业
*/
void initWorks(int size) {workTimesnew int[size];for(int i0; isize; i) {cout输入作业的时长endl;cinworkTimes[i];}
}
/*
*比较函数
*/
bool cmp(const int l1, const int l2) {return l1l2;
}/*
*调度
* size: 作业多少
* count:机器数量
*/
int attemper(int size,int count) {int totalTime0;int minTime0;int minInitworkTimes[0];int k0;vectorint vec;for(int i0; isize;) {//查找空闲机器for(int j0; jcount; j) {if( workTimes[i]!0 machines[j]-1 ) {//安排作业machines[j]i;//记录已经安排的作业vec.push_back(i);i;}}//找最小时长作业minTimeminInit;for(int j0; jvec.size(); j) {if( workTimes[ vec[j] ] !0 workTimes[ vec[j] ] minTime ) {minTime workTimes[ vec[j] ];//记下作业编号kvec[j];}}totalTimeminTime;//清除时间for(int j0; jvec.size(); j) {if(workTimes[vec[j]]minTime )workTimes[vec[j]]-minTime;}for(int j0; jcount; j) {//机器复位为闲if(machines[j]k)machines[j]-1;}}//最大值int ma0;for(int i0; isize; i) {if(workTimes[i]!0 workTimes[i]ma )maworkTimes[i];}totalTimema;return totalTime;
}
/*
*测试
*/
int main() {cout请输入作业个数endl;int size;cinsize;initWorks(size);//对作业按时长大到小排序sort(workTimes,workTimessize,cmp);cout请输入机器数量endl;int count0;cincount;//初始为空闲状态machinesnew int[count] ;for(int i0; icount; i)machines[i]-1;int res attemper(size,count);coutres;return 0;
}
4.背包问题
背包问题是类型问题不是所有的背包问题都能使用贪心算法。
不能分割背包问题也称为0,1背包问题不能使用贪心算法。可分割的背包问题则可以使用贪心算法。
问题描述
现有一可容纳重量为 w的背包且有不同重量的物品且每一个物品都有自己的价值请问怎么选择物品才能保证背包里的价值最大化。
如果物品不可分则称为0~1问题不能使用贪心算法因为贪心算法无法保证背包装满。一般采用动态规划和递归方案。
如果物品可分则可以使用贪心算法本文讨论是可分的情况。
分析问题
既然可以使用贪心算法则现在要考虑贪心策略。
4.1 贪心策略
物品的有 2 个属性
重量。价值。
直观的策略有 2 个
贪重量先放重量最轻的或重量最重的。显然这个策略是有问题的。以重为先相当于先放较重的石头再放较经的金子。以轻为先相当于先放一堆类似于棉花的物品最后再放金子。都无法得到背包中的价值最大化。贪价值以价值高的优先理论上可行。但是如果以纯价值优先如下图所示无法让背包价值最大化。因为把物品 3、物品4、物品 5 一起放入背包总价值可以达到254且背包还可以容纳其它物品。 显然以纯价值优先是不行。
为什么以纯价值优先不行
因为没有把价值和重量放在一起考虑。表面上一个物品的价值是较大的这是宏观上的感觉。但是这个物品是不是有较高的价值应该从重量和价值比考虑也就是价值密度。 Tips 一块铁重10克价值为 100。一块金子重 1 克价值为 90。不能仅凭价值这么一个参数就说明铁比金子值钱。 所以应该以重量、价值比高的物品作为贪心策略。
4.2 编码实现
#includeiostream
#include algorithm
using namespace std;
/*
*物品类型
*/
struct Goods {//重量double weight;//价值double price;void desc() {cout物品重量:this-weight物品价值this-price;}
};//所有物品
Goods allGoods[10];
//物品数量
int size;
//背包重量
int bagWeight;
//存储结果,初始值为 0
double result[10] {0.0};/*
*初始化物品
*/
void initGoods() {for(int i0; isize; i) {cout请输入物品的重量、价值endl;cinallGoods[i].weightallGoods[i].price;}
}/*
*用于排序的比较函数
*/
bool cmp( const Goods g1,const Goods g2) {//按重量价值比return g1.price/g1.weightg2.price/g2.weight;
}
/*
*贪心算法求可分割背包问题
*/
void knapsack() {int i0;for(; isize; i) {if( allGoods[i].weightbagWeight ) {//如果物品重量小于背包重量记录下来result[i]1;//背包容量减小bagWeight- allGoods[i].weight;} else//退出循环break;}//如果背包还有空间if(bagWeight!0) {result[i]bagWeight/allGoods[i].weight;}
}
/*
*显示背包内的物品
*/
void showBag() {double maxValue0;for(int i0; isize; i) {if( result[i] 0)continue;allGoods[i ].desc();maxValueallGoods[i ].price*result[i];cout数量result[i]endl;}cout总价值maxValueendl;
}
/*
*测试
*/
int main() {cout请输入物品数量endl;cinsize;cout请输入背包最大容纳重量endl;cinbagWeight;initGoods();//排序sort(allGoods,allGoodssize,cmp);knapsack();showBag();
}输出结果
5. 过河
问题描述
有一艘小船每次只能载两个人过河。其中只能一人划船渡河的时间等于其中划船慢的那个人的时间。现给定一群人和他们的划船时间请求解最小全部渡河的时间。
分析问题
可根据人数分情况讨论。如下n表示人数
当总人数n3时
n1 tt[1]。只有一个人时过河时间为此人划船时间。n2 tmax(t[1],t[2])。当只有二个人时 1和2中耗时长的那个。n3 tt[1]t[2]t[3] 。 1和3先去,1回来,再和2去。
否则按划船的时间由快到慢排序。
基本原则回来时选择最快的。
1最快和n最慢先去1最快回来1和n-1次慢去1(最快)的回来 n-2 用时2*t[1]t[n]t[n-1]。 1最快和2次快去1(最快)回来n和n-1去2回来 n-2 用时t[1]2*t[2]t[n]。 每次取两种方法的最小耗时直到n3。
编码实现
#include algorithm
#include iostream
using namespace std;//每个人的过河时间
int times[100];/*
*初始化过河时间
*/
void initTimes(int size) {for(int i0; isize; i) {cout输入时间endl;cintimes[i];}
}/*
*比较函数
*/
bool cmp(const int i, const int j) {return ij;
}/*
*贪心算法计算过河最短时间
*/
int river(int size) {int totalTime0;int i0;int jsize-1;while(1) {if(j-i2)break;int t12*times[0]times[j]times[j-1];int t2times[0]2*times[1]times[j];totalTimemin(t1,t2);j-2;}if(j0)totalTime times[0];if(j1)totalTime max(times[0],times[1] );if(j2)totalTimetimes[0]times[1]times[2];return totalTime;
}int main() {cout过河人数:endl;int size0;cinsize;initTimes(size);//排序sort(times,timessize,cmp);int res river(size);cout最短时间res;return 0;
}输出结果 6. 总结
贪心算法在很多地方就可看其身影。如最短路径查找、最小生成树算法里都用到贪心算法。
贪心算法的关键在于以什么属性优先贪心策略这个选对了后续实现都很简单。
