贪心算法

一、基本概念：

     所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

     贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

    所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

二、贪心算法的基本思路：

    1.建立数学模型来描述问题。

    2.把求解的问题分成若干个子问题。

    3.对每一子问题求解，得到子问题的局部最优解。

    4.把子问题的解局部最优解合成原来解问题的一个解。

三、贪心算法适用的问题

      贪心策略适用的前提是：局部最优策略能导致产生全局最优解。

    实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。

四、贪心算法的实现框架

    从问题的某一初始解出发；

    while （能朝给定总目标前进一步）

    { 

          利用可行的决策，求出可行解的一个解元素；

    }

    由所有解元素组合成问题的一个可行解；

五、贪心策略的选择

     因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。

1.最大值最小化 

题目的意思就是给出ｍ个数，分成ｋ组，只能连续的分成一组。求分组中和的最大值最小。 
思路：二分枚举最大值，然后划分的每一组尽量接近这个枚举的值，最大值尽量小。 
这道题的核心部分是二分枚举，贪心主要体现在尽量靠近枚举的值
 

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
const int maxn = 505;
long long l, r, n, group;
int a[maxn];
int vis[maxn];
bool judge(long long x) {

    int k = 1, i;
    long long sum = 0;
    for(i=0; i<n; i++) {

        if(sum + a[i] <= x) {

            sum += a[i];
        }else {

            k++;
            sum = a[i];
        }
        if(k>group) return false;
    }
    return true;
}

void print() {


    memset(vis, 0, sizeof(vis));
    int k = 1,i;
    long long sum=0;
    for(i=n-1; i>=0; i--) {

        if(sum+a[i]<=l) {
            sum += a[i];
        }else {

            k++;
            sum = a[i];
            vis[i] = 1;
        }
    }
    for(i=0; i<n-1&&k<group; i++) {

        if(!vis[i]) {

            vis[i]=1;
            k++;
        }
    }
    for(i=0; i<n; i++) {

        if(i!=n-1) {

            printf("%d ", a[i]);
            if(vis[i]) {

                printf("/ ");

            }
        }
        else printf("%d\n", a[i]);
    }
}
int main() {

    int kase;
    scanf("%d", &kase);
    while(kase--) {

        long long sum = 0;
        long long m = 0;
        int i;
        scanf("%d%d", &n, &group);
        for(i=0; i<n; i++) {

            scanf("%d", &a[i]);
            sum += a[i];
            m = a[i]>m?a[i]:m;
        }
        l=m, r=sum;
        while(r>l) {
            long long mid = (l+r)/2;
            if(judge(mid)) {
                r=mid;
            }else l=mid+1;
        }
        print();

    }
}

2.尽量少的资源消耗 

有一块草坪，长为l，宽为w，在它的水平中心线上有n个位置可以安装喷水装置，各个位置上的喷水装置的覆盖范围为以它们自己的半径ri为圆。求出最少需要的喷水装置个数。 
区间覆盖问题 
代码：

#include<cstdio>
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 10005;
int n;
double l, w;
double p, r;
int num;
double cal() {
    return sqrt(r*r-w*w/4.0);
}
struct node {
    double le, ri;
    bool operator<(const node& c)const {
        return le<c.le;
    }
}arr[maxn];
int main() {
    while(scanf("%d%lf%lf", &n, &l, &w) != EOF) {
        num=0;
        for(int i=0; i<n; i++) {
            scanf("%lf%lf", &p, &r);
            if(r<=w/2) continue;
            double t=cal();
            arr[num].le=p-t;
            arr[num].ri=p+t;
            num++;
        }
        double le=0, ri=0;
        int flag=0, ans=0;
        sort(arr,arr+num);
        if(arr[0].le<=0) {
            int i=0;
            while(i<num) {
                int j=i;
                while(j<num && arr[j].le<=le) {
                    if(ri<arr[j].ri) ri=arr[j].ri;
                        j++;
                }
                if(i==j) break;
                le = ri;
                i=j;
                ans++;
                if(ri>=l) 
                {
                    flag = 1;
                    break;
                }
            }
        }
        if(flag) printf("%d\n", ans);
        else printf("-1\n");

    }
    return 0;
}

3.多机调度问题 

公司要你要完成N份任务，但是你是不可能全部完成的，所以需要雇佣别人来做，做到剩下M份时，自己再亲自出马。现在有个机构，有两种付费方式，第一种是每付A元帮你完成1份，第二种是每付B元帮你完成剩下任务的一半。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 105;
char str[maxn];
int n, m, l;
struct node {

    char name[maxn];
    int half;
    int per;
    int money;
}p[maxn];

void deal (int j) {

    int k = 0,i;
    for (i = 0; i < strlen (str); i++) {

        if (str[i] != ':')
            k++;
        else
            break;  
    }
    memcpy (p[j].name, str, sizeof (str));
    p[j].name[k] = '\0';

    int sum = 0;
    for (i = k + 1; i < strlen (str); i++) {

        if (str[i] != ',')
            sum = sum * 10 + str[i] - '0';
        else {

            p[j].per = sum;
            sum = 0;
        }
    }
    p[j].half = sum;   
}

void cal(int cur) {

    int num = n;
    int sum = 0;
    while(num/2>=m && (p[cur].per*(num-num/2))>=p[cur].half) {
        sum += p[cur].half;
        num/=2;
    }
    sum += (num-m)*p[cur].per;
    p[cur].money = sum;
}


int cmp (const node & x, const node & y) {

    if (x.money < y.money)
        return true;
    else if (x.money > y.money)
        return false;
    else return strcmp (x.name, y.name) < 0 ? true: false;
}
int main() {

    int kase;
    int cas = 1;
    scanf("%d", &kase);
    int i, j;
    while(kase--) {
        printf("Case %d\n", cas++);
        scanf("%d%d%d", &n, &m, &l);
        getchar();
        for(i=0; i<l; i++) {
            gets(str);
            deal(i);
            cal(i);

        }
        sort(p, p+l, cmp);
        for (j = 0; j < l ; j++)
            printf ("%s %d\n", p[j].name, p[j].money);

    }

    return 0;
}

4.最小生成树 

题目：把所有的点连起来最短 
1. Kruskal

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath> 
using namespace std;
const int N = 105;
double x[N], y[N];
struct edge {
    double x, y, d;
}e[N*N];
int f[N];
double ans;
double dis(double x1, double y1, double x2, double y2) {
    return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}
int n;
int num;
int cmp(edge a, edge b) {
    return a.d < b.d;
}
int find(int x) {
    return (x == f[x])?x:find(f[x]);
}
void uni(int a, int b) {

    f[a] = find(b);
}

void ki() {
    ans = 0;
    for(int i=0; i<n; i++) f[i] = i;
    for(int i=0; i<num; i++) {
        int a = find(e[i].x);
        int b = find(e[i].y);
        if(a != b) {
            uni(a,b);
            ans += e[i].d;
        }
    }
    printf("%.2lf\n", ans);
}

int main() {
    int cas; 
    scanf("%d", &cas);
    while(cas--) {
        num = 0;
        scanf("%d", &n);
        for(int i=0; i<n; i++) {
            scanf("%lf%lf", &x[i], &y[i]);
        }
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++) {
                if(i != j) {
                e[num].x = i;
                e[num].y = j;
                e[num++].d = dis(x[i], y[i], x[j], y[j]);
                }
            }
        sort(e, e+num, cmp);
        ki();
        if(cas) printf("\n");
    }

    return 0;
}

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int inf = 0xFFFFFFF;
double x[105], y[105], g[105][105];
int vis[105];
double d[105];
double ans;
int n;
double dis(double x1, double y1, double x2, double y2) {
    return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}
void prim() {
    for(int i=0; i<n; i++) d[i] = g[0][i];
    d[0] = 0;
    memset(vis, 0, sizeof(vis));
    double m;
    int x = 0;

    for(int i=0; i<n; i++) {
        m = inf;
        for(int j=0; j<n; j++) {
            if(d[j]<m && !vis[j]) {
                m = d[j];
                x = j;
            }
        }
        if(m==inf) break;
        ans += m;
        vis[x] = 1;
        for(int j=0; j<n; j++) {
            if(d[j]>g[j][x] && !vis[j]) d[j] = g[j][x];//集外任意一点到已经纳入集合内的点在重调一次距离
        }
    }
}

int main() {
    int cas;
    scanf("%d", &cas);
    while(cas--) {
        memset(g, 0, sizeof(g));
        scanf("%d", &n);
        for(int i=0; i<n; i++) {
            scanf("%lf %lf", &x[i], &y[i]);
        }
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++) {
                g[i][j] = dis(x[i], y[i], x[j], y[j]);
            }
        ans = 0;
        prim();
        printf("%.2lf\n", ans);
        if(cas) printf("\n");
    }
    return 0;
}

5.最短路径

#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n, m, s, d;
const int maxn = 200005;
const int inf = 0x3f3f3f3f;
struct node {
    int n,w;
    node(){}
    node(int a,int b) {
        n=a;
        w=b;
    }
    bool operator<(const node& q)const {

        return w>q.w;
    }
};
vector<node>v[maxn];
int dis[maxn];
void dijkstra() {
    int i;
    int ans = 0;
    dis[s] = 0;
    priority_queue<node>q;
    q.push(node(s,0));
    while(!q.empty()) {

        node u = q.top();
        q.pop();
        for(i=0; i<v[u.n].size(); i++) {
            node temp = v[u.n][i];//遍历每个点
            if(dis[temp.n]>dis[u.n]+temp.w) {
                dis[temp.n] = dis[u.n]+temp.w;//w是从u.n到temp.n的权重
                q.push(temp);
            }
        }

    }
}
int main() {
    int kase;
    int t=1;
    int i,j;
    int a,b,c;
    scanf("%d", &kase);
    while(kase--) {
        scanf("%d%d%d%d", &n,&m,&s,&d);
        for(i=0; i<=n; i++) v[i].clear();
        memset(dis, inf, sizeof(dis));
        for(i=0; i<m; i++) {

            scanf("%d%d%d", &a,&b,&c);
            v[a].push_back(node(b,c));
            v[b].push_back(node(a,c));

        }
        dijkstra();
        printf("Case #%d: ", t++);  
        if (dis[d] < inf)  
            printf("%d\n", dis[d]);  
        else  
            printf("unreachable\n");  
    }
    return 0;
}