【干货】基本概念贪心算法存在的问题04-10-12

01

基本概念

贪心算法意味着当解决一个问题时，它总是在当下做出最好的选择。也就是说，它不考虑整体最优性，只在一定意义上做出局部最优解。贪心算法不能得到所有问题的整体最优解。关键是贪心策略的选择。选择的贪心策略必须没有后遗症，即某个状态的前一个过程不会影响未来的状态，只与当前状态相同。有关的。

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。需要注意的是，贪心算法不能得到所有问题的整体最优解，选择的贪心策略一定是没有后遗症的（即某个状态之后的过程不会影响之前的状态，只与当前状态有关. )

因此，必须仔细分析所采用的贪婪策略是否满足没有后遗症。

02 贪心算法的基本思想

解决问题的一般步骤是：

1.建立数学模型来描述问题；

2. 将要解决的问题分成几个子问题；

3. 求解每个子问题，得到子问题的局部最优解；

4.将子问题的局部最优解合成为原问题的解。

03 算法问题

04 贪心算法应用问题

贪心策略的前提是局部最优策略可以导致全局最优解。

在实践中，贪心算法适用于极少数情况。一般要分析一个问题是否适合贪心算法，可以先选取问题下的几个实际数据进行分析，然后再进行判断。

05 贪婪的选择性质

所谓贪心选择性，就是要寻求的问题的整体最优解可以通过一系列局部最优选择。换句话说，在考虑做出哪个选择时，我们只考虑当前问题的最佳选择，而不考虑子问题的结果。这是贪心算法起作用的第一个基本要素。贪心算法以迭代的方式进行连续的贪心选择，每个贪心选择都将问题简化为一个更小的子问题。对于一个具体的问题，要确定它是否具有贪心选择的性质，必须证明每一步所做的贪心选择最终导致问题的整体最优解。

当一个问题的最优解包含其子问题的最优解时，就称该问题具有最优子结构性质。问题的最优子结构属性是贪心算法可以解决问题的关键特征。

06 贪心算法的实现框架

从问题的初始解决方案开始：

while (朝给定总目标前进一步){利用可行的决策，求出可行解的一个解元素。}

一个可行的问题解决方案是由所有解决方案元素组成的；

07实例分析

如果您熟悉动态规划，您会发现它们之间的相似之处。大多数最优解问题可以一一划分为子问题。解空间的遍历被看作是对子问题树的遍历，通过某种形式遍历整棵树可以得到最优解。在大多数情况下，这是不可行的。贪心算法和动态规划本质上是对子问题树的剪枝。两种算法都要求问题具有的一个属性是子问题的最优性（每个子问题的解构成最优解，因为这个子问题本身肯定是最好的）。动态规划方法代表了这类问题的一般解决方案。我们自下而上构造子问题的解，并且对于每个子树的根，找到下面每个叶子的值，并取其中的最优值作为自己的值。值，其他值被丢弃。贪心算法是动态规划方法的一个特例，它可以证明每个子树的根的值不依赖于后面叶子的值，而只依赖于当前的问题。换句话说，你可以在不知道节点的所有子树的情况下找到节点的值。由于贪心算法的这个特点，它不需要自下而上遍历解空间树，而只需要从根开始，选择最优路径，一路走到底。贪心算法是动态规划方法的一个特例，它可以证明每个子树的根的值不依赖于后面叶子的值，而只依赖于当前的问题。换句话说，你可以在不知道节点的所有子树的情况下找到节点的值。由于贪心算法的这个特点，它不需要自下而上遍历解空间树，而只需要从根开始，选择最优路径，一路走到底。贪心算法是动态规划方法的一个特例，它可以证明每个子树的根的值不依赖于后面叶子的值，而只依赖于当前的问题。换句话说，你可以在不知道节点的所有子树的情况下找到节点的值。由于贪心算法的这个特点，它不需要自下而上遍历解空间树，而只需要从根开始，选择最优路径，一路走到底。

废话不多说，我们来看几个具体的例子来慢慢理解：

1.活动选择题

这是Introduction to Algorithms中的一个例子，也是一个非常经典的问题。有 n 个活动 a1, a2, …, an 需要在同一天使用同一个教室，并且教室一次只能由一个活动使用。每个活动 ai 都有一个开始时间 si 和一个结束时间 fi。一旦被选中，活动 ai 将占据半开时间间隔 [si, fi)。如果 [si,fi] 和 [sj,fj] 不重叠，则可以在这一天安排两个活动 ai 和 aj。问题是如何安排这些活动c语言右结合性，以便尽可能多地举行活动而不会发生冲突。例如下图所示的活动集S，其中活动按结束时间单调递增的顺序排列。

考虑使用贪心算法的解决方案。为方便起见，我们使用不同颜色的线来表示每个活动。行的长度是活动所占用的时间段。蓝线代表我们选择的活动；红线代表我们没有选择的活动。

如果我们每次都选择开始时间最早的活动，我们无法得到最优解：

如果我们每次都选择持续时间最短的活动，我们无法得到最优解：

可以通过数学归纳表明，我们的贪心策略每次都应该选择结束时间最早的活动。直观地说，以这种方式选择兼容的活动也可以为计划外的活动留出尽可能多的时间。这就是为什么活动按结束时间单调递增的原因。

#include#include#includeusing namespace std;    int N;struct Act    {int start;int end;    }act[100010];
bool cmp(Act a,Act b){  return a.end<b.end;      }
int greedy_activity_selector(){  int num=1,i=1;   for(int j=2;j<=N;j++)          {  if(act[j].start>=act[i].end)              {                  i=j;                  num++;              }          }  return num;    }
int main(){  int t;scanf("%d",&t);while(t--)        {scanf("%d",&N);for(int i=1;i<=N;i++)            {scanf("%lld %lld",&act[i].start,&act[i].end);            }            act[0].start=-1;            act[0].end=-1;             sort(act+1,act+N+1,cmp);int res=greedy_activity_selector();cout<<res<<endl;          }    }  

2.硬币找零问题

这个问题在我们的日常生活中比较常见。假设分别有1元、2元、5元、10元、20元、50元、100元的c0、c1、c2、c3、c4、c5、c6纸币。现在用这笔钱支付K元，需要多少张钞票？使用贪心算法的思想，很明显每一步都可以用一张大面值的钞票来做。我们在日常生活中自然而然地这样做。在程序中，Values已经按照从小到大的顺序排列。

#include#includeusing namespace std;const int N=7;int Count[N]={3,0,2,1,0,3,5};int Value[N]={1,2,5,10,20,50,100};
int solve(int money){int num=0;for(int i=N-1;i>=0;i--)        {int c=min(money/Value[i],Count[i]);            money=money-c*Value[i];            num+=c;        }if(money>0) num=-1;return num;    }
int main(){int money;cin>>money;int res=solve(money);if(res!=-1) cout<<res<<endl;else cout<<"NO"<<endl;    }

3.再谈背包问题

在从零开始学习动态规划时，我们已经讲过三个最基本的背包问题：零一背包、部分背包和完全背包。很容易证明背包问题不能使用贪心算法。但是，我们考虑了这样的背包问题：选择项目I将其加载到背包中时，我可以选择该项目的一部分，而不一定全部。然后可以使用贪心算法来解决它。计算每个物品的单位重量值作为贪心选择的依据，选择单位重量值最高的物品，尽可能多的放入背包。这种策略一直持续到背包装满为止。贪心选择在零一背包问题中不能得到最优解的原因是贪心选择不能保证背包最终能被完全装满，部分闲置的背包空间减少了每公斤背包空间的价值. 在程序中，单位重量值已经按降序排列。

    #include   using namespace std;   const int N=4;  void knapsack(float M,float v[],float w[],float x[]);  
int main(){  float M=50;//背包所能容纳的重量   float w[]={0,10,30,20,5};//每种物品的重量  float v[]={0,200,400,100,10};  //每种物品的价值float x[N+1]={0};  //记录结果的数组        knapsack(M,v,w,x);  cout<<"选择装下的物品比例："<<endl;  for(int i=1;i<=N;i++) cout<<"["<<i<<"]:"<<x[i]<<endl;      }  
void knapsack(float M,float v[],float w[],float x[]){  int i;  //物品整件被装下  for(i=1;i<=N;i++)        {  if(w[i]>M) break;               x[i]=1;              M-=w[i];          }   //物品部分被装下  if(i<=N) x[i]=M/w[i];       }

4.多机调度问题

由 n 个作业组成的作业集可以由 m 台相同的机器处理。需要给出一个作业调度方案，使得给定的 n 个作业可以在最短的时间内被 m 台机器处理。作业不能拆分为更小的子作业；每个作业都可以在任何机器上处理。这个问题是NP完全的，没有有效的解（寻找最优解），但是可以使用贪心选择策略设计更好的逼近算法（寻找次优解）。nm 时，首先将 n 个作业从大到小排序，然后按顺序将作业分配给空闲的处理器。也就是说，从剩下的jobs中，选择需要处理时间最长的一个，然后依次选择处理时间最长的一个，直到处理完所有job，或机器无法再处理其他作业。如果我们每次都将处理时间最短的作业分配给一台空闲的机器，可能会出现其他作业都处理完，只剩下处理时间最长的作业，这势必会降低效率。n和m的大小关系在下面的代码中不讨论，两种情况合二为一。

#include  #include    using namespace std;  int speed[10010];  int mintime[110];  
bool cmp( const int &x,const int &y){  return x>y;      }  
int main(){  int n,m;         memset(speed,0,sizeof(speed));  memset(mintime,0,sizeof(mintime));  cin>>n>>m;  for(int i=0;i>speed[i];          sort(speed,speed+n,cmp);  for(int i=0;i<n;++i)           {            *min_element(mintime,mintime+m)+=speed[i];              }   cout<<*max_element(mintime,mintime+m)<<endl;    }

5.船过河问题

POJ1700 是贪心算法的经典例子。问题的主要思想是只有一艘船可以乘坐2人。船的速度是2个人中较慢的一个的速度。经过后，需要一个人将船划回去。询问将 n 个人运送到另一边需要多长时间。首先将大家过河所需的时间按升序排序。我们考虑将最需要时间单独过河的两名旅行者送到对岸。有两种方法：

1.最快第二快过河，然后最快排回船；第二慢最慢过河，然后第二快排回去，所需时间为：t[0]+2*t[1]+t[n-1]；

2.过河最快最慢，后划船最快，过河最快次慢，后划船最快，所需时间为：2*t [0]+t[n-2]+t[n-1]。

如果您进行数学计算，您会知道在其他情况下会花费更多时间。每次运送时间最长的两个人而不影响其他人时，问题具有贪婪子结构的性质。

交流代码：

#include#includeusing namespace std;
int main(){int a[1000],t,n,sum;scanf("%d",&t);while(t--)        {scanf("%d",&n);            sum=0;for(int i=0;i<n;i++) scanf("%d",&a[i]);while(n>3)            {                sum=min(sum+a[1]+a[0]+a[n-1]+a[1],sum+a[n-1]+a[0]+a[n-2]+a[0]);                n-=2;            }if(n==3) sum+=a[0]+a[1]+a[2];else if(n==2) sum+=a[1];else sum+=a[0];printf("%dn",sum);        }    }

6.区间覆盖问题

POJ1328 是贪心算法的经典例子。标题的要点是假设海岸线是一条无限延伸的直线。陆地在海岸线的一侧，海洋在另一侧。每个小岛都是海洋上的一个点。雷达位于海岸线上，只能覆盖d距离，所以如果可以覆盖岛屿，它们之间的距离最多为d。该问题要求计算可以覆盖所有给定岛屿的最小雷达数量。对于每个岛屿，我们可以计算出雷达所在的间隔。

问题变成了如何用尽可能少的点覆盖这些间隔。首先根据左端点的大小对所有区间进行排序，最初需要一个点。如果两个区间相交没有重叠，我们不需要做任何事情；如果一个区间完全包含在另一个区间中，我们需要更新区间的右端点；如果两个区间不相交，我们需要添加点并更新正确的端点。

交流代码：

#include#include#includeusing namespace std;struct Point    {double x;double y;    }point[1000];
int cmp(const void *a, const void *b){return (*(Point *)a).x>(*(Point *)b).x?1:-1;    }
int main(){int n,d;int num=1;while(cin>>n>>d)        {int counting=1;if(n==0&&d==0) break;for(int i=0;i<n;i++)            {int x,y;cin>>x>>y;if(y>d)                {                    counting=-1;                }double t=sqrt(d*d-y*y);//转化为最少区间的问题                point[i].x=x-t;//区间左端点                point[i].y=x+t;//区间右端点            }if(counting!=-1)            {                qsort(point,n,sizeof(point[0]),cmp);//按区间左端点排序double s=point[0].y;//区间右端点for(int i=1;i<n;i++)                {if(point[i].x>s)//如果两个区间没有重合,增加雷达数目并更新右端点                    {                        counting++;                        s=point[i].y;                    }else if(point[i].y<s)//如果第二个区间被完全包含于第一个区间,更新右端点                    {                        s=point[i].y;                    }                }            }cout<<"Case "<<num<<':'<<' '<<counting<<endl;            num++;        }    }

7.销售比赛

关于学校OJ的一个比较好的问题，这里是代码。假设有偶数天，要求每天必须买入或卖出一项，且只能选择且必须选择一项操作，且一开始手头没有该项。现在给你每日项目价格表并要求计算最大收益。首先要明白的是，你必须在第一天买，在最后一天卖，最后手头没有东西。然后除第一天和最后一天外，每次取两天，买小卖大，把卖价放到最小堆里。如果您购买的数量超过堆栈顶部，则交换。这样，我们保证卖价永远大于买价，一定会达到最大的利润。

#include#include#include#include#include#include#includeusing namespace std;long long int price[100010],t,n,res;
int main(){        ios::sync_with_stdio(false);cin>>t;while(t--)        {cin>>n;            priority_queue<long long int, vector, greater > q;            res=0;for(int i=1;i<=n;i++)            {cin>>price[i];            }            res-=price[1];            res+=price[n];for(int i=2;i<=n-1;i=i+2)            {long long int buy=min(price[i],price[i+1]);long long int sell=max(price[i],price[i+1]);if(!q.empty())                {if(buy>q.top())                    {                        res=res-2*q.top()+buy+sell;                        q.pop();                        q.push(buy);                        q.push(sell);                    }else                    {                        res=res-buy+sell;                        q.push(sell);                    }                }else                {                    res=res-buy+sell;                    q.push(sell);                }            }     cout<<res<<endl;        }    }

下面我们结合数据结构方面的知识来解释几个例子。

8.霍夫曼编码

这也是“算法简介”中的一个例子。霍夫曼编码是一种非常有效的编码方法，广泛用于数据文件压缩。我们可以通过多种方式表示文件中的信息。如果我们用01字符串来表示字符，用定长编码来表示，我们需要3位来表示一个字符，整个文件编码需要30万位；我们用变长编码来表示高频字符 用较短字符的编码和用低频字符的较长编码达到减少整体编码的目的，那么整个文件编码需要（45×1+13×3+12 ×3+16×3+9×4+5× 4)×1000=224000 bits，可以看出变长编码比定长编码方案好，

每个字符都指定一个 01 字符串作为其代码，任何字符的代码都不是其他字符代码的前缀。此代码称为前缀代码。也许无前缀代码会是一个更好的名称，但前缀代码是公认的标准术语。代码的前缀性质可以让解码变得非常简单：比如001011101可以唯一分解成0、0、101、1101，所以解码为aabe。解码过程需要轻松取出代码的前缀。为此，可以使用二叉树作为前缀码的数据结构：叶子代表一个给定的字符；从根到叶子的路径作为字符的前缀码；将代码0或1中的每个位的代码作为路标，分别指示节点的左侧或右侧。

从上图可以看出，最优前缀编码的二叉树始终是完全二叉树，而定长编码的二叉树并不是完全二叉树。给定编码字符集 C 和频率分布 f，C 的前缀编码方案对应于二叉树 T。树 T 中字符 c 的深度表示为 dT(c)，dT(c) 也是字符 c 的前缀码长度。那么平均码长定义为：

使平均码长最小的前缀码编码方案称为C的最优前缀码。

Huffman编码的构造方法：首先合并频率最小的2个字符对应的子树，计算合并子树的频率；重新排序子树；合并上述排序的子树序列；所有节点合并成一棵完整的二叉树；0、1 赋值给二叉树中的边，得到每个字符的变长码。

POJ3253就是使用这种思想的典型例子。标题的主要思想是将无限长的木板锯成几个给定长度的小木板。每次锯切都需要一定的成本，成本就是当前锯切板的长度。给定每个所需小板的长度和小板的数量，找到最小成本。以要求长度为5、8、5的3块板为例：先从无限板中锯出一块长度为21的板，成本为21；然后从长度为 21 的板上看到长度为 5 的板，成本为 5；然后从长度为 16 的木板中锯出长度为 8 的木板，成本为 8；总成本 = 21+5+8=34。使用霍夫曼的思想，为了使总成本最小化，每次只选择两个长度最小的板并将它们加在一起，然后将这些和加到总成本中。为了效率，

交流代码：

#include#include#includeusing namespace std;
int main(){long long int sum;int i,n,t,a,b;while(~scanf("%d",&n))        {            priority_queue<int,vector,greater >q;for(i=0;i<n;i++)            {scanf("%d",&t);                q.push(t);            }            sum=0;if(q.size()==1)            {                a=q.top();                sum+=a;                q.pop();            }while(q.size()>1)            {                a=q.top();                q.pop();                b=q.top();                q.pop();                t=a+b;                sum+=t;                q.push(t);            }printf("%lldn",sum);        }    }

9.Dijkstra 算法

Dijkstra 算法由 EWDijkstra 于 1959 年提出，目前被公认为求解最短路径的最佳方法。使用的条件是图中不能有负边。该算法解决了从单个源点到其他顶点的最短路径问题。它的主要特点是每次迭代中选择的下一个顶点是标记点外离源点最近的顶点，简单来说就是bfs+贪心算法的思想。

#include#include#define INF 1000#define MAX_V 100using namespace std;  
int main(){int V,E;int i,j,m,n;int cost[MAX_V][MAX_V];int d[MAX_V];bool used[MAX_V];cin>>V>>E;        fill(d,d+V+1,INF);        fill(used,used+V,false);for(i=0;i<V;i++)        {for(j=0;j<V;j++)            {if(i==j) cost[i][j]=0;else cost[i][j]=INF;            }        }for(m=0;m<E;m++)        {cin>>i>>j>>cost[i][j];            cost[j][i]=cost[i][j];        }cin>>n;        d[n]=0;//源点while(true)        {int v=V;for(m=0;m<V;m++)            {    if((!used[m])&&(d[m]<d[v])) v=m;            }    if(v==V) break;            used[v]=true;for(m=0;m<V;m++)            {                d[m]=min(d[m],d[v]+cost[v][m]);            }        }for(i=0;i<V;i++)        {cout<<"the shortest distance between "<<n<<" and "<<i<<" is "<<d[i]<<endl;        }    }

10.最小生成树算法

假设一个网络表示为一个无向连通加权图 G = (V, E) ，E 中每条边 (v, w) 的权重为 c[v][w]。如果G的子图G’是一棵包含G所有顶点的树，那么G’称为G的生成树。生成树的代价是指生成树上边权重的总和。在 G 的所有生成树中，代价最小的生成树称为 G 的最小生成树。例如，在设计通信网络时，图的顶点用来表示城市，权重 c[v边(v,w)的][w]用来表示在城市v和城市w之间建立一条通信线路的成本，最小生成树给出了构建通信网络的最经济的解决方案。

构造最小生成树的 Kruskal 算法和 Prim 算法都利用了 MST（最小生成树）属性：设顶点集 U 是 V 的一个真子集（可以任意选择），如果 (u, v) ∈ E是跨度点集U和VU的边，即u∈U，v∈VU，在所有这样的边中c语言右结合性，(u,v)的权重c[u][v]最小，则G Spanning tree 中一定有一棵最小的树，它有 (u, v) 作为边之一。

这个性质可以很容易地用反证法证明。假设对于G的任意最小生成树T，对于点集U和VU，(u,v)∈E是跨越这两个点集的最小权重边，T不包含最小权重边，但T包含节点u和 v. 将被添加到树 T 中，这将成为一个带有循环的子图，并且该循环具有不同的边，u’∈U，v’∈VU。将被删除，得到另一棵树T’，即用 替换T中的边得到树T’。由于这两条边的cost满足c[u][v]≤c[u’][v’]，T’cost≤Tcost，这与T是任意最小生成树的假设相矛盾，因此得到证明。

Prim算法的每一步都选择连接U和VU权重最小的边加入生成树。

#include#include#define MAX_V 100#define INF 1000using namespace std;  
int main(){int V,E;int i,j,m,n;int cost[MAX_V][MAX_V];int mincost[MAX_V];bool used[MAX_V];cin>>V>>E;        fill(mincost,mincost+V+1,INF);        fill(used,used+V,false);for(i=0;i<V;i++)        {for(j=0;j<V;j++)            {if(i==j) cost[i][j]=0;else cost[i][j]=INF;            }        }for(m=0;m<E;m++)        {cin>>i>>j>>cost[i][j];            cost[j][i]=cost[i][j];        }        mincost[0]=0;int res=0;while(true)        {int v=V;for(m=0;m<V;m++)            {    if((!used[m])&&(mincost[m]<mincost[v]))                    v=m;            }    if(v==V) break;            used[v]=true;            res+=mincost[v];for(m=0;m<V;m++)            {                mincost[m]=min(mincost[m],cost[v][m]);            }        }cout<<res<<endl;    }

Kruskal算法的每一步都直接将权重最小的非循环边加入到生成树中，借助联合搜索的数据结构我们可以完美的实现。

#include#include#define MAX_E 100using namespace std;  struct edge    {int u,v,cost;        };int pre[MAX_E];    edge es[MAX_E];int find(int x);void initvalue(int x);bool same(int x,int y);void unite(int x,int y);bool comp(const edge& e1,const edge& e2);
int main(){int V,E;int i,j,m,n;cin>>V>>E;        initvalue(V);for(i=0;i>es[i].u>>es[i].v>>es[i].cost;                sort(es,es+E,comp);int res=0;for(i=0;i<E;i++)        {            edge e=es[i];if(!same(e.u,e.v))            {                unite(e.u,e.v);                res+=e.cost;            }        }cout<<res<<endl;        }
bool comp(const edge& e1,const edge& e2){return e1.cost<e2.cost;        }
void initvalue(int x){for(int i=0;i<x;i++) pre[i]=i;    }
int find(int x){int r=x;while(pre[r]!=r) r=pre[r];int i=x,j;while(pre[i]!=r)        {            j=pre[i];            pre[i]=r;            i=j;        }return r;    }
bool same(int x,int y){if(find(x)==find(y)) return true;else return false;        }
void unite(int x,int y){int fx=find(x);int fy=find(y);if(fx!=fy) pre[fx]=fy;        }

来源：CSDN、简书等

‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧  END  ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧
关注我的微信公众号，回复“C语言”免费领取300G编程资料。


点击“阅读原文”查看更多分享，欢迎点分享、收藏、点赞、在看

百度未收录