貪心算法：從多個方面深入探究

一、什麼是貪心算法

貪心算法是一種常見的算法思想，在很多問題中都有應用。貪心算法是一種直觀而且簡單的算法，通過每一步選擇中都採取最優的選擇來達到整體最優的解。

貪心算法思路比較單一，每次選擇都是當前狀態下的最優選擇，因此複雜度通常較低。但是，貪心算法的正確性較難證明，很多問題並不是貪心選擇一定是最優解，需要對每個問題進行分析。

貪心算法用於解決那些具有最有子結構性質的問題，即問題可以分解為更小的子問題，每個子問題的最優解可以遞推得到整個問題的最優解。

二、貪心算法的基本思想

貪心算法要求在每一步選擇中都採取最優的選擇，而得到問題的最優解。

貪心算法通常分為兩個階段：

建立數學模型來描述問題，找到最優解的性質；
利用貪心思想，每一步都做出局部最優的選擇，從而達到全局最優。

貪心算法的核心是在每一步選擇中都採取最優的選擇，但此時必須具有無後效性。即某個狀態以及之前的狀態所做的選擇，不會影響以後的狀態。只需要考慮當前狀態下的最優解，和之前的選擇無關。

三、貪心算法的應用

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;
}