贪心算法介绍

贪心算法，顾名思义，就是采取贪心的策略去解决或者优化问题。其主要思想是：保证每次操作都是局部的最优解，从而得到全局最优解。（但其实从字面上来看，贪心显然不是一个好词，他仅仅局限于当下，而不是去纵观全局，因此，有时候贪心算法并不能得到全局最优解。）

贪心算法的思路

我们首先肯定是要确定我们的贪心目标，比如性价比最高的商品，或者最短的时间，或者最少的钱。然后，我们按照这个目标，一步一步的进行贪心选择，直到我们达到目标。

贪心算法的应用

背包问题洛谷P2240

这里还是把题目写出来吧

题目描述

阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 $N(N \le 100)$ 堆金币，第 $i$ 堆金币的总重量和总价值分别是 $m_i,v_i(1\le m_i,v_i \le 100)$。阿里巴巴有一个承重量为 $T(T \le 1000)$ 的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？

输入格式

第一行两个整数 $N,T$。

接下来 $N$ 行，每行两个整数 $m_i,v_i$。

输出格式

一个实数表示答案，输出两位小数

输入输出样例 #1

输入 #1
1
2
3
4
5
4 50
10 60
20 100
30 120
15 45
输出 #1
1
240.00

思路

注意到题目说了，所有金币都可以随意分割，分割完的金币重量价值比不变。因此，我们可以先对金币按照价值从小到大排序，然后从后往前遍历（为什么不从大到小排序呢？因为sort()函数默认是从小到大排序的，我比较懒），如果当前的金币的重量小于等于背包的容量，我们就把它装进去，并更新背包的容量和价值。如果当前的金币的重量大于背包的容量，我们就停止装了，因为装不下了。

这里我们使用结构体来打包金币的信息，包括重量和价值以及性价比。
然后要写一个排序函数来告诉sort()函数我们要按照结构体中的价值进行排序。

1
2
3
4
5
6
7
8
9
struct Item {
    int weight;
    int value;
    double ratio;
};

bool cmp(Item a, Item b) {
    return a.ratio > b.ratio;
}

感觉这一步应该是最关键的，也是最麻烦的（对于一个rookie来说）。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

struct Item {
    int weight;
    int value;
    double ratio;
};

bool cmp(Item a, Item b) {
    return a.ratio > b.ratio;
}

int main() {
    int N, T;
    cin >> N >> T;
    vector<Item> items(N);
    for (int i = 0; i < N; i++) {
        cin >> items[i].weight >> items[i].value;
        items[i].ratio = (double)items[i].value / items[i].weight;
    }
    sort(items.begin(), items.end(),cmp);
    double total = 0.0;
    for (int i = 0; i < N && T > 0; i++) {
        if (items[i].weight <= T) {
            total += items[i].value;
            T -= items[i].weight;
        } else {
            total += items[i].ratio * T;
            T = 0;
        }
    }
    printf("%.2f\n", total);
    return 0;
}