本节学习目标：贪心算法的概念以及对应练习题

 贪心算法概念

贪心算法的特点

 利用贪心算法的两个性质

 练习1：最优装载问题

 【本题算法分析】

优先把重量小的物品放进去，在容量固定的情况下，装的物品量最多。
因此采用重量最轻者先装的贪心选择策略，可从局部最优达到全局最优。

参考代码

#include <iostream>
#include <algorithm>
using namespace std;
int w[1010];
int main() {
    int c, n, cnt = 0;
    cin >> c >> n;
    for(int i = 0; i < n; i++){
        cin >> w[i];
    }
    sort(w,w + n);
    for(int i = 0; i < n; i++){
        if(c - w[i] < 0){
            break;
        }
        c -= w[i];
        cnt++;
    }
    cout << cnt;
    return 0;
}

 练习2：粮草

【算法分析】
优先选择价格低的粮草，在需要的总量固定的情况下，总的消费最少。
因此采用优先选择价格低的粮草的贪心选择策略，可从局部最优达到全局最优。

【参考代码】

#include <iostream>
#include <algorithm>
using namespace std;

struct node{
    int p;
    int a;
}b[5010];

bool cmp(node x, node y){
    if(x.p < y.p) return true;
    else return false;
}

int main() {
    int n, m, sum = 0;
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        cin >> b[i].p >> b[i].a;
    }
    sort(b + 1, b + m + 1, cmp);
    for(int i = 1; i <= m; i++){
        if(n - b[i].a <= 0){
            sum += n * b[i].p;
            break;
        }
        n -= b[i].a;
        sum += b[i].a * b[i].p;
    }
    cout << sum;
    return 0;
}

  练习3：接水问题

【算法分析】
平均等待时间 = 总等待时间 / n。
当第 i 个接水的人在接水的时候，等待的人数为 n-i，为了总等待时间最少，应该让接水时间短的人先接水，这样其他人等待的时间就会最少。

因此采用接水时间最短者先接水的贪心选择策略，可从局部最优达到全局最优

【参考代码】
#include <iostream>
#include <algorithm>
using namespace std;

struct node{
    int t;
    int id;
}a[1010];

bool cmp(node x, node y){
    if(x.t < y.t) return true;
    else return false;
}

int main() {
    int n;
    cin >> n;
    double sum = 0; 
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        a[i].t = x;
        a[i].id = i;
    }
    sort(a + 1, a + n + 1, cmp);
    for(int i = 1; i <= n; i++){
        cout << a[i].id << " ";
        sum += a[i].t * (n - i);
    }
    cout << endl;
    printf("%.2f", sum / n);
    return 0;
}

  练习4：书架

【算法分析】
优先选择身高高的奶牛，在书架高度固定的情况下，奶牛的数量最少。
因此采用身高最高者先选择的贪心选择策略，可从局部最优达到全局最优。

【参考代码】
#include <iostream>
#include <algorithm>
using namespace std;

int a[20010];

bool cmp(int x, int y){
    if(x > y) return true;
    else return false;
}

int main() {
    int n, b;
    cin >> n >> b;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    sort(a+1,a+n+1,cmp);
    int sum = 0, cnt = 0;
    for(int i = 1; i <= n; i++){
        if(sum + a[i] >= b){
            cnt++;
            break;
        }
        sum += a[i];
        cnt++;
    }
    cout << cnt;
    return 0;
}

 练习5：数列乘积变1术

【算法分析】
采用优先把小于 0 的数则变为 −1，大于 0 的数则变为 1 的贪心策略。

如果序列中 -1 的个数为奇数，则判断序列中是否存在 0，不存在说明需要将其中一个 -1 加 2 变为 1，总的花费加 2。

【参考代码】
#include <iostream>
using namespace std;

long long n, cnt, sum;

int main() {
    cin >> n;
    int flag = 0; 
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        if(x < 0){ //小于0则变为-1 
            cnt++;
            sum += (-1) - x;
        } else if(x > 0){ //大于0则变为1 
            sum += x - 1;
        } else {   //等于0，变为-1或者1，标记出现过0 
            sum++;
            flag = 1;
        }
    }
    if(cnt % 2 == 1 && flag == 0) cout << sum + 2; //奇数个-1并且序列中没有0，则需将其中一个 -1 加2，总的花费加2 
    else cout << sum;
    return 0;
}

贪心算法总结