贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。

贪心算法不是对所有问题都能得到体最优解，关键是整贪心策略的选择

贪心算法一般按如下步骤进行：  

①建立数学模型来描述问题   。

②把求解的问题分成若干个子问题   。

③对每个子问题求解，得到子问题的局部最优解   。

④把子问题的解局部最优解合成原来解问题的一个解   。

贪心算法实际应用---零钱找回问题

这个问题在我们的日常生活中很普遍。

假设1元、2元、5元、10元、20元、50元、100元的纸币分别有

c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？

用贪心算法的思想，很显然，每一步尽可能用面值大的纸币即可。在日常生活中我们自然而然也是这么做的。在程序中已经事先将Value按照从小到大的顺序排好。

#include <iostream>

#include <math.h>

using namespace std;

int single_money[7]={1,2,5,10,20,50,100};

int number_money[7]={2,5,1,3,4,0,4};

//每种面值使用贪心后的张数

int count[7]={};

int total_count;

int tanxin(int money)

{

      if(money>=0)

      {

             for(int i=6;i>=0;i--)

             {

                    count[i]=min(number_money[i],money/single_money[i]);

                    money=money-count[i]*single_money[i];

             }

             return 0;

      }

      else

      {

             return money;

      }

     

 }

 int main()

 {

     int money;

     cout<<"please input the amount of money";

     cin>>money;



            if(!tanxin(money))

              {

                          cout<<"贪心最优结果为："<<endl;

                          for(int j=6;j>=0;j--)

                          {

       

                                 cout<<single_money[j]<<"元:"<<count[j]<<"张"<<endl;

                           }

       

            }

            else

            {

                   cout<<"ops,wrong number";

            }



             return 0;

}

贪心算法实际应用---活动安排问题

活动选择问题:这是《算法导论》上的例子，也是一个非常经典的问题。

有n个需要在同一天使用同一个教室的活动a1,a2,…,an，教室同一时刻只能由一个活动使用。

每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。

如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。

该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。例如下图所示的活动集合S，其中各项活动按照结束时间单调递增排序。

#include <iostream>

#include <algorithm>

using namespace std;



//定义活动的集合,Act 为抽象数据类型名，activity 为实例数据

//结构体

struct Act

{

      int start;

      int end;

} activity[100];



int N;//活动的个数

 //给出了排序方法                                                                                                                                                                                                                                                                          

bool cmp(Act a,Act b)

{

      return a.end<b.end;

}



int greedy()

{

      int num=0;

      //要在排序之后实现

      for (int i=0,j = i+1;i<N;++j)

      {

             if (activity[j].start > activity[i].end )

             {

                    i = j;

                    num++;

             }

      }

      return num;

}



int main(int argc,char** argv)

{

      //问题的初始化

      cout<<"The total num of activities:";

      cin>>N;

      cout<<"Please input the start and end time of each activity:";

      for (int i = 0;i<N;++i)

      {

             cin>>activity[i].start;

             cin>>activity[i].end;

      }



      //将活动按结束时间排序，cmp为排序标准，sort也可以只有两个参数

      sort(activity,activity+N,cmp);



      //输出结果

      int res = greedy();

      cout<<"The maximum activities can be hold is "<<res;

      system("pause");

      return 0;

}

经典算法中的贪心

          单源路径中的Djikstra算法

注意核心：1.一旦一个点已经被选定，就代表它到起点的最短距离已经确定了，不会再更改

          2.每次比较的距离是从起点出发的路径，而不是单独比较以选定点为起点的边

        下面例题，以D为起点

第一步，D到C最短，将C加入集合S

        此时集合S有C，D

第二步，距离分别是，<D,E>=4,<D,C,F>=9,<D,C,E>=8,<D,C,B>=13

        将E点加入S

第三步，距离分别为，<D,C,F>=9,<D,C,B>=13,<D,E,F>=6,<D,E,G>=12

        将F加入S

第四步，距离分别为，<D,C,B>=13,<D,C,F,A>=25,<D,C,F,G>=18,<D,C,F,B>=16,<D,E,G>=12,<D,E,F,A>=22,<D,E,F,B>=13

        将G加入S

第五步，距离分别为，<D,C,B>=13,<DE,F,A>=22,<D,E,G,A>=26

        将B加入S

第六步，<D,C,B,A>=25,<D,E,F,A>=22,<D,E,G,A>=26

        将A加入S

 

#include<stdio.h>
  #include<string.h>
  #define inf 0x3f3f3f3f
  int map[110][110],dis[110],visit[110];
 /*
  关于三个数组：map数组存的为点边的信息，比如map[1][2]=3，表示1号点和2号点的距离为3
 dis数组存的为起始点与每个点的最短距离，比如dis[3]=5，表示起始点与3号点最短距离为5
 visit数组存的为0或者1，1表示已经走过这个点。
 */
 int n,m;
 int dijstra()
{
   int i,j,pos=1,min,sum=0;
    memset(visit,0,sizeof(visit));//初始化为.，表示开始都没走过
    for(i=1; i<=n; ++i)
     {
         dis[i]=map[1][i];
     }
     visit[1]=1;
     dis[1]=0;
     for(i=1; i<n; i++)
     {
         min=inf;
         for(j=1; j<=n; ++j)
         {
           if(visit[j]==0&&min>dis[j])
             {
                 min=dis[j];
                 pos=j;
             }
         }
        visit[pos]=1;//表示这个点已经走过
         for(j=1; j<=n; ++j)
         {
             if(visit[j]==0&&dis[j]>dis[pos]+map[pos][j])//更新dis的值
                 dis[j]=dis[pos]+map[pos][j];
         }
     }
     return dis[n];
 }
 int main()
 {
     int i,j;
     while(~scanf("%d%d",&n,&m),n||m)//n表示n个点，m表示m条边
     {
         for(i=1; i<=n; ++i)
         {
             for(j=1; j<=n; ++j)
             {
                map[i][j]=inf;//开始时将每条边赋为最大值
             }
         }
         int a,b,c;
         for(i=1; i<=m; ++i)
         {
             scanf("%d%d%d",&a,&b,&c);
             if(c<map[a][b])//防止有重边
                 map[a][b]=map[b][a]=c;
         }
        int count=dijstra();
         printf("%d\n",count);
    }     return 0;
 }

 

 

 

 

最小生成树Prim算法

lowcost[i]:表示以i为终点的边的最小权值,当lowcost[i]=0说明以i为终点的边的最小权值=0,也就是表示i点加入了MST

mst[i]:表示对应lowcost[i]的起点，即说明边<mst[i],i>是MST的一条边，当mst[i]=0表示起点i加入MST

 

 

第一步，以V1为起点，lowcost[2]=6,lowcost[3]=1,lowcost[4]=5

                       Mst[2]=1,mst[3]=1,mst[4]=1

                     MST中有V1，再加入V3

第二步，经过比较后更新，比如<v1,v2>=6 > <v3,v2>=5，所以low cost[v2]=5.

                      Lowcost[2]=5,lowcost[3]=0,lowcost[4]=5,lowcost[5]=6,

                      Lowcost[6]=4

                      Mst[2]=3,mst[3]=0,mst[4]=1,mst[5]=3,mst[6]=3

                      MST 中有V1，V3，再加入V6

第三步，经过比较后，更新，Lowcost[2]=5,lowcost[3]=0,lowcost[4]=2,lowcost[5]=6,

                      Lowcost[6]=0

                      Mst[2]=3,mst[3]=0,mst[4]=6,mst[5]=3,mst[6]=0

                      MST中有V1，V3，V6，再加入V4

第四步，经过比较后，更新，Lowcost[2]=5,lowcost[3]=0,lowcost[4]=0,lowcost[5]=6,

                      Lowcost[6]=0

                      Mst[2]=3,mst[3]=0,mst[4]=0,mst[5]=3,mst[6]=0

                      MST中有V1，V3，V6，V4，再加入V2

第五步，经过比较后，更新，Lowcost[2]=0,lowcost[3]=0,lowcost[4]=5,lowcost[5]=3,

                      Lowcost[6]=0

                      Mst[2]=0,mst[3]=0,mst[4]=0,mst[5]=2,mst[6]=0

                       MST中有V1，V3，V6，V4，V2，再加入V5

可得生成树如上。注意此算法考虑的不是从出发点到该点的距离，而是考虑以该点为终点的权值，以及记住该边的起始点。

#include<iostream>

#include<fstream>

using  namespace std;



#define MAX 100

#define MAXCOST 0x7fffffff



int graph[MAX][MAX];//距离表格

//lowcost[i]:表示以i为终点的边的最小权值,当lowcost[i]=0说明以i为终点的边的最小权值=0,也就是表示i点加入了MST

//mst[i]:表示对应lowcost[i]的起点，即说明边<mst[i],i>是MST的一条边，当mst[i]=0表示起点i加入MST

int prim(int graph[][MAX], int n)

{

      int lowcost[MAX];

      int mst[MAX];//

      int i, j, min, minid, sum = 0;

      for (i = 2; i <= n; i++)

      {

             lowcost[i] = graph[1][i];

             mst[i] = 1;

      }

      mst[1] = 0;

      for (i = 2; i <= n; i++)

      {

             min = MAXCOST;

             minid = 0;

             for (j = 2; j <= n; j++)

             {

                    if (lowcost[j] < min && lowcost[j] != 0)

                    {

                           min = lowcost[j];

                           minid = j;

                    }

             }

             cout << "V" << mst[minid] << "-V" << minid << "=" << min << endl;

             sum += min;

             lowcost[minid] = 0;

             for (j = 2; j <= n; j++)

             {

                    if (graph[minid][j] < lowcost[j])

                    {

                           lowcost[j] = graph[minid][j];

                           mst[j] = minid;

                    }

             }

      }

      return sum;

}



int main()

{

      int i, j, k, m, n;

      int x, y, cost;

      ifstream in("input.txt");

      in >> m >> n;//m=顶点的个数，n=边的个数

      //初始化图G

      for (i = 1; i <= m; i++)

      {

             for (j = 1; j <= m; j++)

             {

                    graph[i][j] = MAXCOST;

             }

      }

      //构建图G

      for (k = 1; k <= n; k++)

      {

             in >> i >> j >> cost;

             graph[i][j] = cost;

             graph[j][i] = cost;

      }

      //求解最小生成树

      cost = prim(graph, m);

      //输出最小权值和

      cout << "最小权值和=" << cost << endl;

      system("pause");

      return 0;

}

 

 

 

最小生成树 Kruskal算法(加边法)

 

 

与Prim算法不同，Kruskal算法是保留点，一条一条加边

第一步，选取<v0,v4>

第二步，选取<v1,v2>

第三步，选取<v1,v5>

第四步，选取<v1,v5>

依次类推，直到所有点都访问到

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

using namespace std;

int parent[10];

int n,m;

int i,j;



struct edge{

      int u,v,w; //边的顶点，权值

}edges[10];



//初始化并查集

void UFset(){

      for(i=1; i<=n; i++) parent[i] = -1;

}



//查找i的跟

int find(int i){

      int temp;

      //查找位置

      for(temp = i; parent[temp] >= 0; temp = parent[temp]);

      //压缩路径

      while(temp != i){

             int t = parent[i];

             parent[i] = temp;

             i = t;

      }

      return temp;

}

//合并两个元素a,b

void merge(int a,int b){

      int r1 = find(a);

      int r2 = find(b);

      int tmp = parent[r1] + parent[r2]; //两个集合节点数的和

      if(parent[r1] > parent[r2]){

             parent[r1] = r2;

             parent[r2] = tmp;

      }else{

             parent[r2] = r1;

             parent[r1] = tmp;

      }

}



void kruskal(){

      int sumWeight = 0;

      int num = 0;

      int u,v;

      UFset();

      for(int i=0; i<m; i++)

      {

             u = edges[i].u;

             v = edges[i].v;



             if(find(u) != find(v)){ //u和v不在一个集合

                    printf("加入边：%d %d,权值： %d\n", u,v,edges[i].w);

                    sumWeight += edges[i].w;

                    num ++;

                    merge(u, v); //把这两个边加入一个集合。

             }

      }

      printf("weight of MST is %d \n", sumWeight);

}



//比较函数，用户排序

int cmp(const void * a, const void * b){

      edge * e1 = (edge *)a;

      edge * e2 = (edge *)b;

      return e1->w - e2->w;

}



int main() {



      scanf("%d %d", &n, &m);

      for(i=0; i<m; i++){

             scanf("%d %d %d", &edges[i].u,  &edges[i].v,  &edges[i].w);

      }

      qsort(edges, m, sizeof(edge), cmp);



      kruskal();





      return 0;

}

//kruskal 算法也是贪心，考虑的是边

 

推荐内容
阅读全文
AI总结
# 贪心算法 # 图论 # 算法
Logo
GitCode 开源社区

旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。

更多推荐

cover

大学生摸鱼暂停！G-Star 校园开发者计划，喊你上车啦?

avatar GitCode 开源社区
cover

G-Star 校园开发者计划·黑科大｜开源第一课之 Git 入门

avatar GitCode 开源社区
cover

小胰宝 PancrePal 强势加入 GitCode！开启开源抗癌新纪元

avatar GitCode 开源社区