概念：

局部最优

题目

• 1. 分发饼干 (easy 455)

思路：

image.png

给最小孩子以能满足的最小饼干

代码：

方法一：
时间复杂度为O(n^2)；

using namespace std;
int MaxChildren(vector<int>&children,vector<int>&cookies){
    int ans=0;
    sort(children.begin(),children.end());
    sort(cookies.begin(),cookies.end());
    for(int i=0;i<children.size();i++){
        for(int j=0;j<cookies.size();j++){
            if(children[i]<=cookies[j]){
                ans++;
                cookies[j]-=children[i]:
            }
        }
    }
    return ans;
}

方法二：
时间复杂度

using namespace std;

int MaxChildren(vector<int>&children,vector<int>&cookies){
    int ans=0;
    makeheap(children.begin(),children.end(),greater<int>);
    makeheap(cookies.begin(),cookies.end(),greater<int>);
    for(int i=0;i<children.size();i++){
        for(int j=0;j<cookies.size();j++){
            pop_heap(children.begin(),children.end(),greater<int>);
            pop_heap(cookies.begin(),cookies.end(),greater<int>);  
            if(children[-1]<=cookies[-1]){
                ans++;
                cookies[-1]-=children[-1];
                children.pop_back();
                cookies.pop_back(); 
                //若饼干可以吃剩下的
                //if(cookies[-1]==0) { cookies.pop_back(); }
            }
            else{ cookies.pop_back();  }
        }
    }
    return ans;

• 2.股票的最大收益

思路：

f[4]-f[1]=(f[4]-f[3])+(f[3]-f[2])+(f[2]-f[1])
即局部最优可以保证全局最优，因此可以使用贪心。

from 知乎

代码：

int MaxInterest(vector<int>& prices){
  int ans=0;
  for(int i=1;i<prices.size();i++){
    if(prices[i]>prices[i-1]){ans+=prices[i]-prices[i-1];}  
  }
  return ans;
}

• 种植问题：

代码：

bool canPlant(vector<int>& plant,int n){
  if(n<=0)return true;
  int i=0;
  if(plant[plant.size()-1]==0&&plant[plant.size()-2]==0){n--;plant[plant.size()-1]=1;}
  while(i<plant.size()){
    if(plant[i-1]=0&&plant[i+1]=0)n--;
    if(n==0)return true;
    i++;
    }
  return false;

• Kruskal和Prim算法

Kurskal算法思想：对边排序，每次取最小边，若不构成环路则加入，所有点入集合时循环终止
伪代码：

void Krukskal(Grap& map,vector<string>&Kvertex){
  sort(map);
  int i=0,j=0;
  vector<vector<int>>&Tvertex;
  while(i<num){
    if(Tvertex[map[j][0]][map[j][1]]==0){
      Kvertex[++i]=to_string([map[j][0]])+(string)[map[j][1]]；
      Tvertex[map[j][0]][map[j][1]]==1;
    }
    j++;
  }
}

Prim算法思想：取点的最小边，更新点集合，每次取集合的最小邻边，所有点入集合时循环终止
代码：

 vector<int> Prim(Grap &G){
    int count=1,v=0;
    vector<int>(num,0)w;
    while(count<G.num){
        v=Sort(w,G,count);//Sort,在G种，取w的前count个元素的临边，找到最小值，返回最小值的临边；
        w[count++]=v;
    }
    return w;

• Dijikstra算法

思想：取点的最小边，更新点集合，再更新到当前点的最短距离；和Prim类似，区别在于会更新最小距离。

image.png

代码：

void Dij(Graph &G,int start, vector<int>Dist){
  int n=G.num;
  vector<int>Final(num,0);
  vector<int>Path(num,-1);
  Final[start]=1;
  Path[start]=-1;
  Dist[start]=0;
  int min_value=Maxsize;
  int min_index=start;
  while(Ture){
      int flag=0;
      for(int i=0;i<n;i++){
          if(Final[i]){
              for(int j=0;j<n;j++){
                  if(Dist[i]+G[i][j]<Dist[i]) { 
                      Dist[i]= (Dist[i]+G[i][j];
                      Path[j]=i; 
                  }  
                }
            }
            else{
                min_value=Dist[i]>min_value?min_value:Dist[i];
                min_index=i;
            }
      }
      Final[min_index]=1;
      for(int i=0;i<n;i++){
          if(!Final[i]){flag=1;}
      }
      if(flag=0)break;
    }
}

Dijkstra堆优化: