贪心算法：从多个方面深入探究

一、什么是贪心算法

贪心算法是一种常见的算法思想，在很多问题中都有应用。贪心算法是一种直观而且简单的算法，通过每一步选择中都采取最优的选择来达到整体最优的解。

贪心算法思路比较单一，每次选择都是当前状态下的最优选择，因此复杂度通常较低。但是，贪心算法的正确性较难证明，很多问题并不是贪心选择一定是最优解，需要对每个问题进行分析。

贪心算法用于解决那些具有最有子结构性质的问题，即问题可以分解为更小的子问题，每个子问题的最优解可以递推得到整个问题的最优解。

二、贪心算法的基本思想

贪心算法要求在每一步选择中都采取最优的选择，而得到问题的最优解。

贪心算法通常分为两个阶段：

• 建立数学模型来描述问题，找到最优解的性质；
• 利用贪心思想，每一步都做出局部最优的选择，从而达到全局最优。

贪心算法的核心是在每一步选择中都采取最优的选择，但此时必须具有无后效性。即某个状态以及之前的状态所做的选择，不会影响以后的状态。只需要考虑当前状态下的最优解，和之前的选择无关。

三、贪心算法的应用

1、背包问题

背包问题是一类经典的贪心算法问题，通常有两种类型：0/1背包问题和完全背包问题。

对于0/1背包问题，每个物品只能选一次。物品有两个限制，一个是总重量不能超过背包的最大承重，另一个是每个物品的重量和价值都不相同。贪心策略是每次选取价值比较高的物品放进背包，直到不能再加为止。这样可以获得比较好的解，但不一定是最优解。

完全背包问题中，每个物品可以选择多次放入背包中。这种问题可以转换为一个贪心问题，每次选取价值比较高的物品，直到背包无法再放下为止。

#include
using namespace std;

struct node{
    int w;//重量
    int v;//价值
};

int cmp(node a, node b){
    return a.v > b.v;//按价值从大到小排序
}

double knapsack(node a[], int n, int m){
    double ans = 0.0;
    int i;
    sort(a, a+n, cmp);
    for(i=0; i
    m) break;
        else{
            ans += a[i].v;//先选价值最大的物品
            m -= a[i].w;
        }
    }
    if(i < n){
        ans += (double)(a[i].v) * m / a[i].w;//计算部分装或全装时的最优价值
    }
    return ans;
}

int main(){
    int n, m;
    cin>>n>>m;//n个物品，m为背包容量
    int i;
    node a[n];
    for(i=0; i
    >a[i].w>>a[i].v;
    }
    printf("%.2lf", knapsack(a, n, m));
    return 0;
}

    
   
  

2、活动选择问题

活动选择问题是一种常见的贪心算法问题，也被称为区间调度问题。该问题要求安排一个学生参加尽可能多的互不冲突的活动，以达到时间上最合理的目的。

具体实现方法是按照每个活动的结束时间从小到大排序，然后依次选择最早结束的活动，直到无法再加入为止。

#include
#include
   
using namespace std;

struct activity{
    int start;//开始时间
    int end;//结束时间
};

bool cmp(activity a, activity b){
    return a.end
    >n;
    activity a[n];
    int i;
    for(i=0; i
     >a[i].start;
        cin>>a[i].end;
    }
    sort(a, a+n, cmp);//按结束时间从小到大排序
    int cnt=1;
    int last=a[0].end;
    for(i=1; i
      =last){
            cnt++;//计算可安排的活动数目
            last=a[i].end;
        }
    }
    cout<
       
        
3、霍夫曼编码
        
霍夫曼编码是一种使用较广泛的编码技术，主要应用于数据压缩。
        
在进行编码时，通常按照每个字符的出现概率从小到大排序。然后使用贪心算法构建一个霍夫曼树，来得到一组字符的编码方式，保证编码长度的最小化和解码的唯一性。
        
#include
#include
          
#include
           
#include
            
using namespace std;

struct node{
    int data;//节点权值
    node* left;//左子节点指针
    node* right;//右子节点指针
};

struct cmp{
    bool operator () (node *a, node *b){
        return a->data > b->data;
    }
};

string code[500];
node* root;

void preorder(node *p, string str){
    if(!p) return;
    if(!p->left && !p->right){
        code[p->data] = str;
    }
    preorder(p->left, str+'0');
    preorder(p->right, str+'1');
}

void build(char a[], int b[], int n){
    int i;
    node *left, *right;
    priority_queue
             , cmp> q;
    for(i=0; i
              
               data = a[i]; p->left = NULL; p->right = NULL; q.push(p); } while(q.size()>1){ left = q.top(); q.pop(); right = q.top(); q.pop(); node *p = new node; p->data = 0; p->left = left; p->right = right; p->data = left->data + right->data; q.push(p);//构建霍夫曼树 } root = q.top(); preorder(root, ""); } int main(){ char a[1000];//只考虑ASCII码部分，总共只有256个字符 int b[1000]; memset(code, 0, sizeof(code));//所有编码初始化为0 int n, i; cin>>n; for(i=0; i
               
                >a[i]>>b[i]; } build(a, b, n);//构建霍夫曼树 for(i=0; i<256; i++){ if(code[i]!=""){ cout<<(char)i<<" "<
                
                 <
                 
                  
4、最小生成树
                  
最小生成树是一个图的子集，可以与所有顶点相连而不形成环，并且权值之和最小。
                  
贪心算法应用非常广泛，其中包括基于贪心策略的Prim算法和Kruskal算法。Prim算法是在新生成的最小生成树中加入一个顶点，然后找到与其相邻的最短边，将其加入最小生成树。Kruskal算法则是将所有边按照权值从小到大排序，依次加入最小生成树中，同时保证之前加入的边不会形成环。
                  
#include
#include
                    
using namespace std;

const int maxn = 1000;
const int inf = 0x3f3f3f;

int eg[maxn][maxn];
int vis[maxn];
int ans;

int prim(int n){
    int i, j, minn;
    vis[1] = 1;//从1开始遍历
    for(i=1; i
                     >n>>m;//n个点，m条边
    int i, j, x, y, w;
    for(i=1; i<=n; i++){
        for(j=1; j
                      >x>>y>>w;//x和y之间的边权值为w
        eg[x][y] = eg[y][x] = w;
    }
    ans = 0;
    cout<
                       


                        
四、贪心算法的局限性


                        
尽管贪心算法在许多问题中应用广泛，但并不是所有问题都适用于贪心思想。贪心算法求得的最优解可能并不是全局最优解。


                        
有一些问题中，每个局部最优解可以得到全局最优。比如霍夫曼编码，贪心算法比较适用。但是对于一些问题，贪心策略可能无法达到全局最优解。比如旅行商问题，这是一个NP问题，通过贪心策略得到的最优解与全局最优解可能存在很大的误差。


                        
因此，在处理这些问题时，需要对每个问题进行判断和分析。同时，可以通过优化贪心策略，得到比较好的局部最优解，来逐步逼近全局最优解。真正的全局最优解通常需要通过枚举或动态规划等方法得到。