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

一、什么是贪心算法

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

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

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

二、贪心算法的基本思想

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

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

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

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

三、贪心算法的应用

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>>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<<cnt;
    return 0;
}

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<node*, vector, cmp> q;
    for(i=0; idata = 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<<" "<<code[i]<<endl;//输出字符对应的编码
        }
    }
    return 0;
}

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; i++){
        minn = inf;
        int u = -1;
        for(j=1; j<=n; j++){
            if(vis[j]){
                for(int k=1; k<=n; k++){
                    if(!vis[k] && eg[j][k] >n>>m;//n个点，m条边
    int i, j, x, y, w;
    for(i=1; i<=n; i++){
        for(j=1; j<n; j++){
            eg[i][j] = inf;
        }
    }
    for(i=0; i>x>>y>>w;//x和y之间的边权值为w
        eg[x][y] = eg[y][x] = w;
    }
    ans = 0;
    cout<<prim(n);//输出最小生成树的权值
    return 0;
}