贪心选择性质

贪心选择性质是指，所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每步所做的贪心选择最终导致问题的整体最优解。

会场安排问题

问题描述

假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。对于给定的k个待安排的活动，给出开始时间和结束时间，计算使用最少会场的时间表。

解题思路

按所有活动开始时间排序，然后遍历，对每个活动，若有会场可以安排，则修改该会场结束时间。若无，则新开会场。时间复杂度O（n*n）。
贪心选择性质：开始时间最早的活动优先安排可让会场数最小。
子问题：安放开始时间最早的活动之后，其余活动的安放。

源代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct item {
    int start, end;
};
struct item a [1010];
int n, t, b [1010];
int cmp (const void *a, const void *b){
    struct item *c = (struct item *)a;
    struct item *d = (struct iten *)b;
    if (c->start != d->start)return c->start - d->start;
    return c->end - d->end;
}
int main()
{
    int i, j, res = 0;
    scanf("%d", &n);
    for (i=0; i<n; i++)scanf("%d%d", &a [i].start, &a [i].end);
    qsort(a, n, sizeof(a [0]), cmp);
    //for (i=0; i<n; i++)printf("%d %d\n", a [i].start, a [i].end);
    for (i=0; i<n; i++){
        for (j=0; j<t; j++){
            if (a [i].start >= b [j]){
                b [j] = a [i].end;
                break;
            }
        }
        if (j==t)b [t++] = a [i].end;
    }
    printf("%d", t);
    return 0;
}

哈夫曼编码问题

问题描述

哈夫曼编码算法是使用字符在文件中出现的次数来建立一个用0、1串表示各字符的最优表示方式。可以实现文件压缩。这里，给定1、2、3、……n字符出现的次数，求解哈夫曼编码。

解题思路

贪心选择性质：每次选择最小的两个结点进行合并可取得最小权值。
子问题：选取最小权值的两结点合并完成后，剩余结点仍然采取此策略进行解决。
时间复杂度：由于使用了堆优化，时间复杂度从O（n）变为O（nlogn）。

源代码

#include <stdio.h>
#include <stdlib.h>
struct jie {
    int v;
    struct jie * left;
    struct jie * right;
    struct jie * par;
};
int n, t, c [1010], tec;
struct jie *a [1010], *b [1010], *p, *q, *r;
void up (int x){
    struct jie *t;
    if (x==1)return ;
    if (a [x]->v < a [x/2]->v){t = a [x]; a [x] = a [x/2]; a [x/2] = t;}
    up(x/2);
}
void down (int x){
    struct jie *t;
    int te = x;
    if (x*2<=n&&a [te]->v>a [x*2]->v)te = x*2;
    if (x*2+1<=n&&a [te]->v>a [x*2+1]->v)te = x*2+1;
    if (te!=x){t = a [x]; a [x] = a [te]; a [te] = t; down(te);}
}
void bianli (struct jie *x){
    if (x==NULL)return ;
    if (x->left==NULL&&x->right==NULL){
        printf("%d : ", x->v);
        for (int i=0; i<t; i++)printf("%d", c [i]); printf("\n");
    }
    c [t++] = 0; bianli(x->left); t--;
    c [t++] = 1; bianli(x->right); t--;
}
int main()
{
    int i, y, m;
    scanf("%d", &m);
    for (i=0; i<m; i++){
        a [++n] = (struct jie *)malloc(sizeof(struct jie)); a [n]->left = a [n]->right = a [n]->par = NULL;
        scanf("%d", &a [n]->v);
        up(n);
    }
    //for (i=1; i<=n; i++)printf("<%d>\n", a [i]->v);
    while (n!=1){
        r = (struct jie *)malloc(sizeof(struct jie));
        p = a [1]; a [1] = a [n--]; down(1);
        q = a [1]; a [1] = a [n--]; down(1);
        p->par = q->par = r;
        r->left = p; r->right = q; r->par = NULL;
        r->v = p->v + q->v;
        a [++n] = r; up(n);
    }
    bianli(a [1]);
    return 0;
}

迪杰斯特拉算法求最短路径

问题描述

这是一个经典的求单源最短路径的问题。给定顶点数和边数，接下来给出各边的两个顶点以及权值。求出各点到指定点的最短路径。这里选定第一个点为指定点。

解题思路

贪心选择性质：每次选取已求解集合外的结点到求解集合最小的距离的边，即为该点的最短距离的解。
子问题：选取一个顶点进行合并后，剩余结点仍采取此策略。
时间复杂度：使用堆优化后，时间复杂度由O（n）变为O（nlogn）。

源代码

#include <stdio.h>
#include<stdlib.h>
int n, m, c [110][110], tem, dis [110], a [110], b [110], vis [110];
int mini (int a, int b){return (a>b)?b:a;}
int maxi (int a, int b){return (a<b)?b:a;}
void up (int x){
    int t;
    if (x==1)return ;
    if (dis [a [x]] < dis [a [x/2]]){t = a [x]; a [x] = a [x/2]; a [x/2] = t;}
    up(x/2);
}
void down (int x){
    int t, te = x;
    if (x*2<=tem&&dis [a [te]]>dis [a [x*2]])te = x*2;
    if (x*2+1<=tem&&dis [a [te]]>dis [a [x*2+1]])te = x*2+1;
    if (te!=x){t = a [x]; a [x] = a [te]; a [te] = t; down(te);}
}
int main () {
    int i, j, v1, v2, ww, bestv;
    scanf("%d%d", &n, &m);
    for (i=0; i<n; i++){
        b [i] = i; dis [b [i]] = 1e9;
    }
    for (i=0; i<n; i++)for (j=0; j<n; j++)if (i!=j)c [i][j] = -1;
    for (i=0; i<m; i++){
        scanf("%d%d%d", &v1, &v2, &ww);
        c [v1-1][v2-1] = ww;
    }
    for (i=0; i<n; i++)if (c [0][i] > 0){dis [b [i]] = c [0][i];}
    //for (i=0; i<n; i++)printf("<<%d %d>>\n", a [i]->hao, a [i]->dis);
    for (i=1; i<n; i++){
        a [++tem] = b [i];
        up(tem);
    }
    //for (i=1; i<=tem; i++)printf("<%d %d>\n", a [i], dis [a [i]]);
    vis [0] = 1; dis [0] = 0;
    while (tem){
        bestv = a [1];
        vis [bestv] = 1;
        a [1] = a [tem--];
        //printf("%d in, dis %d\n", bestv, dis [bestv]);
        //for (i=1; i<=tem; i++)printf("<%d %d>", a [i], dis [a [i]]); printf("\n%d", tem);
        down(1);
        //for (i=1; i<=tem; i++)printf("<%d %d>", a [i], dis [a [i]]); printf("\n");
        for (i=0; i<n; i++)
            if (vis [i] == 0 && c [bestv][i] > 0 && dis [i] > dis [bestv] + c [bestv][i])
                dis [i] = dis [bestv] + c [bestv][i];
    }
    for (i=0; i<n; i++)printf("point 1->%d : %d\n", i+1, dis [i]);
    return 0;
}

多元哈夫曼编码问题

问题描述

在一个操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆，规定每次至少选2堆，最多选k堆石子合并成新的一堆。合并的费用为新的一堆的石子数。设计一个算法，计算出将n堆石子合并成一堆的最大总费用和最小总费用。

解题思路

最大值：
贪心选择性质：每次只合并最大的两堆，可取得最大值。
由于有堆优化，时间复杂度O（nlogn）。
最小值：
贪心选择性质及子问题：使最后的一次合并得到最大权值，剩余部分仍然采用此策略。
由于有堆优化，时间复杂度也为O（nlogn）级别。

源代码

#include <stdio.h>
#include <stdlib.h>
int a [1010], n, m, b [1010], tem;
int maxi (int a, int b){return (a > b) ? a : b;}
void up (int x){
    int t;
    if (x==1)return ;
    if (a [x] < a [x/2]){t = a [x]; a [x] = a [x/2]; a [x/2] = t;}
    up(x/2);
}
void down (int x){
    int t;
    int te = x;
    if (x*2<=tem&&a [te]>a [x*2])te = x*2;
    if (x*2+1<=tem&&a [te]>a [x*2+1])te = x*2+1;
    if (te!=x){t = a [x]; a [x] = a [te]; a [te] = t; down(te);}
}
void up2 (int x){
    int t;
    if (x==1)return ;
    if (a [x] > a [x/2]){t = a [x]; a [x] = a [x/2]; a [x/2] = t;}
    up2(x/2);
}
void down2 (int x){
    int t;
    int te = x;
    if (x*2<=tem&&a [te]<a [x*2])te = x*2;
    if (x*2+1<=tem&&a [te]<a [x*2+1])te = x*2+1;
    if (te!=x){t = a [x]; a [x] = a [te]; a [te] = t; down2(te);}
}
int main () {
    int i, j, res = 0, ne;
    scanf("%d%d", &n, &m);
    for (i=0; i<n; i++)scanf("%d", &b [i]);
    for (i=0; i<n; i++){
        a [++tem] = b [i];
        up(tem);
    }
    //for (i=1; i<=tem; i++)printf("<%d>", a [i]);
    for (i=0; i<(n-2)%(m-1)+2; i++){
        res += a [1];
        a [1] = a [tem--];
        down(1);
    }
    a [++tem] = res; up(tem);
    while (tem>1){
        ne = 0;
        for (i=0; i<m; i++){
            ne += a [1];
            a [1] = a [tem--];
            down(1);
        }
        res += ne;
        a [++tem] = ne; up(tem);
    }
    printf("min : %d\n", res);
    tem = 0; res = 0;
    for (i=0; i<n; i++){
        a [++tem] = b [i];
        up2(tem);
    }
    while (tem>1){
        ne = 0;
        for (i=0; i<2; i++){
            ne += a [1];
            a [1] = a [tem--];
            down2(1);
        }
        res += ne;
        a [++tem] = ne; up2(tem);
    }
    printf("max : %d", res);
    return 0;
}