贪心算法

简介与概述、功能介绍

在信息学竞赛（OI）中，贪心算法是一种高效且常用的算法策略。其核心思想是在每一个决策点都做出当下看起来最优的选择，期望通过一系列这样的局部最优选择，最终达到全局最优的结果。贪心算法的优势在于实现简单、代码量少、运行效率高，能够在较短时间内解决部分复杂问题。然而，并非所有问题都适用贪心算法，只有当问题具有贪心选择性质和最优子结构性质时，贪心算法才能保证得到全局最优解。

适用场景

贪心算法适用于满足以下两个重要性质的问题：

贪心选择性质：问题的全局最优解可以由一系列局部最优选择构成。即在每一个决策时刻，仅考虑当前状态下的最优选择，而无需考虑该选择对后续步骤的影响。
最优子结构性质：问题的最优解包含其子问题的最优解。也就是说，原问题的最优解可以通过子问题的最优解推导得出。

常见的适用贪心算法的问题包括活动选择问题、部分背包问题、区间覆盖问题等。

算法原理详解

贪心算法的基本步骤如下：

分解问题：将原问题分解为一系列相互关联的子问题。
贪心选择：对于每个子问题，依据某种贪心策略做出当前看起来最优的选择。贪心策略的选择至关重要，它直接影响到算法的正确性和效率。
求解子问题：对做出贪心选择后的子问题进行求解。
合并解：将子问题的解合并起来，得到原问题的解。

在实际应用中，关键在于确定合适的贪心策略。一般来说，可以通过分析问题的特点和性质，尝试不同的贪心策略，并通过证明或反例来验证其正确性。

经典例题及代码实现

例题 1：活动选择问题

题面描述：有 $n$ 个活动，每个活动有一个开始时间 $s_i$ 和结束时间 $f_i$ 。要求从这些活动中选择一些活动，使得这些活动两两之间的时间不冲突，并且选择的活动数量最多。
输入样例：

第一行表示活动的数量 $n$ ，接下来的 $n$ 行每行包含两个整数，分别表示活动的开始时间和结束时间。

输出样例：

表示最多可以选择的活动数量。

代码实现：

示例代码

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 1000;

struct Act {
    int s;
    int e;
} act[MAXN];

int n;

bool cmp(Act a, Act b) {
    return a.e < b.e;
}

int sel() {
    sort(act, act + n, cmp);
    int cnt = 1;
    int end = act[0].e;
    for (int i = 1; i < n; i++) {
        if (act[i].s >= end) {
            cnt++;
            end = act[i].e;
        }
    }
    return cnt;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> act[i].s >> act[i].e;
    }
    int res = sel();
    cout << res << endl;
    return 0;
}

例题 2：部分背包问题

题面描述：有一个容量为 $W$ 的背包和 $n$ 个物品，每个物品有一个重量 $w_i$ 和一个价值 $v_i$ 。可以选择将物品的一部分放入背包，要求在不超过背包容量的前提下，使得背包中物品的总价值最大。
输入样例：

第一行包含两个整数 $n$ 和 $W$ ，分别表示物品的数量和背包的容量。接下来的 $n$ 行每行包含两个整数，分别表示物品的重量和价值。

输出样例：

240.00

表示背包中物品的最大总价值。

代码实现：

示例代码

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 1000;

struct Itm {
    int w;
    int v;
} itm[MAXN];

int n, cap;

bool cmp(Itm a, Itm b) {
    return (double)a.v / a.w > (double)b.v / b.w;
}

double solve() {
    sort(itm, itm + n, cmp);
    double val = 0;
    for (int i = 0; i < n; i++) {
        if (cap == 0) break;
        if (itm[i].w <= cap) {
            val += itm[i].v;
            cap -= itm[i].w;
        } else {
            val += (double)cap / itm[i].w * itm[i].v;
            cap = 0;
        }
    }
    return val;
}

int main() {
    cin >> n >> cap;
    for (int i = 0; i < n; i++) {
        cin >> itm[i].w >> itm[i].v;
    }
    double res = solve();
    printf("%.2f\n", res);
    return 0;
}

贪心算法在信息学竞赛中是一种非常实用的算法策略，它具有实现简单、效率高的优点。然而，其应用范围相对较窄，只适用于具有贪心选择性质和最优子结构性质的问题。在使用贪心算法时，关键在于确定合适的贪心策略，并通过证明或反例来验证其正确性。通过不断练习和积累经验，能够更好地掌握贪心算法，提高解决问题的能力。同时，在竞赛中遇到问题时，要仔细分析问题的特点，判断是否适合使用贪心算法，避免盲目使用导致错误的结果。

例题

Status

Problem