路漫 2020-05-07
当面对一个复杂的问题,需要求得问题最优解的时候,贪心法可以高效率的解决问题;
贪心法不是从整体最优考虑,它仅仅是通过一系列在局部看来最好的选择,而得到问题整体的最优解;
贪心法并不是对所有的问题都能得到最优解,但对许多问题它确实能产生整体最优解,而对一些问题即使不能得到整体最优解,也能得到最优解的近似解;
许多经典的算法都是用贪心法设计的,如,哈夫曼算法、Prim算法、Kruskal算法和Dijkstra算法等均是典型的贪心算法,都是利用贪心选择策略得到了问题的最优解;
适用贪心算法解决问题应具有如下两个重要性质:
1、最优子结构性质,当问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质;
2、贪心选择性质,所谓贪心选择性质是指所求问题的整体最优解,可以通过一系列局部最优解的选择(贪心选择)来得到,即,每一步所作出的贪心选择最终可导致问题的整体最优解;
一、活动安排问题
设有n个活动的集合E = {E1,E2,...En},其中各活动需共享同一资源,每一活动Ei均有使用资源的时间要求,起始时间Si,结束时间Fi;若(Si,Fi)与(Sj,Fj)不相交,则活动Ei与Ej相容,资源的管理者只能选择彼此相容的活动进行安排;要求,在给定的活动中选择出最大相容活动子集合(活动个数最多),进行资源分配。
采用贪心选择策略求解问题,对于给定的n个活动{E1,E2,...En},贪心选择策略为:
1、首选结束时间最早的活动Ei,保留与Ei相容的活动,剔除与Ei不相容的活动(活动按结束时间Fi非递减排序);
2、在剩余活动中选择结束时间最早的活动Ej,保留与Ej相容的活动,剔除与Ej不相容的活动(通过活动的结束时间找下一个活动的开始时间,再通过活动的开始时间找下一个活动的结束时间);
重复步骤2,直至全部活动处理完毕。
void GreedySelector(int n,int s[],int f[],bool A[]) { /* A中保存选择结果 */ A[1] = true; int j = 1; for (int i=2; i<=n; ++i) { if(s[i] >= f[j]) { A[i] = true; j = i; } else { A[i] = false; } } }
二、背包问题
给定n种物品和一个背包,已知背包的容量(载重量)为C及各物品的重量wi、价值vi,现求解如何选择装入背包的物品,使得背包中物品的总价值最大。
例,给定3种物品和背包,已知背包的容量为10,物品的重量wi = {6,5,5} (物品均可拆分) ,价值vi = {30,20,15},现要求按背包问题求解,使得装入背包的物品总价值最大。
背包问题可用贪心法求解:
1、求每件物品的单位重量价值:Vi/Wi;
2、按单位重量价值由高至低选装物品,直至装满包;
背包问题的解为{1,4/5,0},物品价值46
物品不可拆分的,不能用贪心法求解