贪心算法

苏丙榅2025-04-012025-04-01

1. 贪心算法概述

贪心算法（Greedy Algorithm）是一种基于局部最优选择的算法设计思想，其核心在于每一步都做出当前看起来最优的选择，并希望通过这些局部最优选择的累积，最终得到全局最优解。它不回溯，也不考虑未来的可能影响，而是“贪心”地选择当前最有利的选项。

在处理某些问题的时候使用贪心算法通常遵循以下步骤：

分解问题：将原问题分解为一系列子问题。
贪心选择：在每一个子问题中，都做出当前看起来最优的选择。
求解子问题：对每一个子问题求解，得到子问题的局部最优解。
合并解：将所有子问题的局部最优解合并起来，得到原问题的解。

贪心算法典型的应用场景:

问题类型	示例	贪心策略
区间调度问题	活动选择、无重叠区间	按结束时间排序，选最早结束的区间
最小生成树	Prim、Kruskal 算法	每次选权重最小的边
最短路径问题	Dijkstra 算法	每次选当前距离起点最近的节点
哈夫曼编码	数据压缩	合并频率最小的字符节点
部分背包问题	物品可分割的背包问题	按单位价值排序，优先选高价值物品

贪心算法与动态规划作为两种重要的算法设计策略，掌握贪心算法和动态规划的区别，能帮助我们在不同场景下做出更合适的算法选择，以下是二者的差异。

贪心算法	动态规划
每一步选择局部最优解	考虑所有可能的子问题
无回溯，效率高	可能需要存储中间结果
适用于部分优化问题	适用于更广泛的优化问题
例如：Dijkstra 算法	例如：Floyd-Warshall 算法

2. 贪心算法典型案例

2.1 区间调度问题

假设有一个会议室，同一时间只能有一个会议使用该会议室。现在有一系列会议的开始时间和结束时间，你需要设计一个算法来安排尽可能多的会议在这个会议室进行。也就是说，要找出最大的会议集合，使得集合中任意两个会议的时间区间都不重叠。

输入：一个包含多个会议的列表，每个会议用一个二元组 (start_time, end_time) 表示，其中 start_time 是会议的开始时间，end_time 是会议的结束时间。

输出：能够安排的最大会议数量。

这个问题可以使用贪心算法来解决。贪心策略是按照会议的结束时间对所有会议进行排序，然后依次选择结束时间最早且与已选择的会议不冲突的会议。

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

struct Meeting
{
    int start;
    int end;
};

bool compareMeetings(const Meeting& a, const Meeting& b)
{
    return a.end < b.end;
}

int maxMeetings(vector<Meeting>& meetings)
{
    if (meetings.empty())
    {
        return 0;
    }

    sort(meetings.begin(), meetings.end(), compareMeetings);
    int count = 1;
    int lastEndTime = meetings[0].end;
    cout << "会议时间: " << meetings[0].start << " - " << meetings[0].end << endl;
    for (int i = 1; i < meetings.size(); ++i)
    {
        if (meetings[i].start >= lastEndTime)
        {
            ++count;
            cout << "会议时间: " << meetings[i].start << " - " << meetings[i].end << endl;
            lastEndTime = meetings[i].end;
        }
    }
    return count;
}

int main()
{
    vector<Meeting> meetings = {
        {1, 4},
        {3, 5},
        {0, 6},
        {5, 7},
        {3, 9},
        {5, 9},
        {6, 10},
        {8, 11},
        {8, 12},
        {2, 14},
        {12, 16}
    };
    int result = maxMeetings(meetings);
    cout << "能够安排的最大会议数量是: " << result << endl;
    return 0;
}

定义会议结构体：Meeting 结构体包含两个成员变量 start 和 end，分别表示会议的开始时间和结束时间。
比较函数：compareMeetings 函数用于按照会议的结束时间对会议进行排序。
贪心算法实现：maxMeetings 函数实现了贪心算法的核心逻辑。首先对会议列表按照结束时间进行排序，然后选择第一个会议作为初始会议，接着遍历剩余的会议，选择开始时间大于等于上一个已选择会议结束时间的会议。
主函数：在 main 函数中，定义了一个示例会议列表，并调用 maxMeetings 函数求解最大会议数量，最后输出结果。

2.2 部分背包问题

有一个背包，它的容量为 W（单位：千克）。现在有 n 种物品，每种物品有其对应的重量 wi（单位：千克）和价值 vi 单位：元），并且每种物品可以被分割成任意比例。也就是说，你可以选择拿走某件物品的一部分，而不是必须拿走整个物品。

问题：在不超过背包容量的前提下，如何选择物品放入背包，使得背包中物品的总价值最大？

输入：

物品数量 n=3

背包容量 W=50

物品信息（重量和价值）：

物品 1：重量 w1=10，价值 v1=60

物品 2：重量 w2=20，价值 v2=100

物品 3：重量 w3=30，价值 v3=120

输出：
最大总价值为 240。具体选择方案为：拿走物品 1 的全部（价值 60），物品 2 的全部（价值 100），物品 3 的 20/30（价值 80）。

解决部分背包问题的贪心策略是：计算每种物品的单位重量价值（价值 / 重量），然后按照单位重量价值从高到低对物品进行排序。接着依次选择单位重量价值高的物品放入背包，直到背包无法再放入完整的物品为止。对于最后一个无法完整放入的物品，可以将其按比例分割后放入背包，以充分利用背包的剩余容量。

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

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

bool compareItems(const Item& a, const Item& b) 
{
    return a.unitValue > b.unitValue;
}

double fractionalKnapsack(int W, vector<Item>& items) 
{
    for (auto& item : items) 
    {
        item.unitValue = static_cast<double>(item.value) / item.weight;
    }

    sort(items.begin(), items.end(), compareItems);

    double totalValue = 0.0;
    for (const auto& item : items) 
    {
        if (W >= item.weight) 
        {
            totalValue += item.value;
            W -= item.weight;
        }
        else 
        {
            totalValue += W * item.unitValue;
            break;
        }
    }
    return totalValue;
}

int main() 
{
    int n = 3;  // 物品数量
    int W = 50; // 背包容量

    vector<Item> items = {
        {10, 60, 0.0},
        {20, 100, 0.0},
        {30, 120, 0.0}
    };
    double maxValue = fractionalKnapsack(W, items);
    cout << "最大总价值为: " << maxValue << endl;
    return 0;
}

结构体 Item：用于存储每种物品的重量、价值和单位重量价值。
比较函数 compareItems：用于对物品按单位重量价值从高到低进行排序。
fractionalKnapsack 函数：
- 首先计算每种物品的单位重量价值。
- 然后对物品进行排序。
- 依次遍历排序后的物品，根据背包剩余容量决定是装入整个物品还是部分物品。
main 函数：初始化物品信息和背包容量，调用 fractionalKnapsack 函数计算最大总价值并输出结果。

2.3 超市找零问题

假设你是一名收银员，需要给顾客找零。现在有不同面值的硬币，分别为 1 元、5 元、10 元、20 元、50 元、100 元。给定需要找零的金额 amount，要求使用最少数量的硬币来完成找零。

示例输入输出

输入：

需要找零的金额 amount = 63

输出：

最少需要的硬币数量为 5，具体组合为 1 个 50 元硬币、1 个 10 元硬币、3 个 1 元硬币。

贪心算法的核心思想是每次都选择面值最大的硬币，直到找零金额为 0。具体步骤如下：

对硬币面值从大到小进行排序。
从最大面值的硬币开始尝试，尽可能多地使用该面值的硬币，直到剩余找零金额小于该面值。
接着尝试使用下一个较小面值的硬币，重复步骤 2，直到找零金额为 0。

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

void coinChange(int amount) 
{
    vector<int> coins = { 100, 50, 20, 10, 5, 1 };
    int coinCount = 0;
    vector<int> usedCoins;

    for (int coin : coins) 
    {
        int numCoins = amount / coin;
        for (int i = 0; i < numCoins; ++i) 
        {
            usedCoins.push_back(coin);
        }
        amount %= coin;
        coinCount += numCoins;
    }

    cout << "最少需要的硬币数量为: " << coinCount << endl;
    cout << "使用的硬币金额分别为: ";
    for (int coin : usedCoins) 
    {
        cout << coin << "元 ";
    }
    cout << endl;
}

int main() 
{
    int amount = 63;
    coinChange(amount);

    return 0;
}

coinChange 函数：
- 首先定义了一个包含所有硬币面值的向量 coins，按从大到小的顺序排列。
- 创建一个空的向量 usedCoins，用于存储实际使用的硬币金额。
- 通过for循环遍历每个硬币面值，对于每个面值的硬币：
  - 计算当前面值硬币最多能使用的数量 numCoins，即 amount / coin。
  - 用一个内层 for 循环将该面值的硬币添加到 usedCoins 向量中 numCoins 次。
  - 更新剩余找零金额 amount %= coin，并累加使用的硬币数量到 coinCount 中。
- 最后输出最少需要的硬币数量，以及具体使用的硬币金额。
main 函数：
- 定义需要找零的金额 amount。
- 调用 coinChange 函数进行找零计算并输出结果。

2.4 外卖小哥的最优送单计划

外卖小哥需要在城市中送 n 份订单，每个订单有 取餐时间 pickup_time 和 送餐截止时间 delivery_time。假设送一单需要固定时间 delivery_duration（例如 30 分钟），且外卖小哥一次只能携带一单（送完才能接下一单）。
目标：设计算法，计算外卖小哥一次最多能完成多少订单。

输入

orders：一个二维数组，orders[i] = [pickup_time_i, delivery_time_i]，表示第 i 个订单的取餐时间和截止时间。

delivery_duration：送一单所需的时间（固定值）。

输出

返回最多能完成的订单数。

使用贪心算法解决这个问题的具体思路如下:

排序订单：按 delivery_time（截止时间）升序排序，优先处理截止时间早的订单。
遍历订单：
- 记录当前时间 current_time（初始为 0）。
- 对于每个订单，检查 pickup_time 是否 ≥ current_time，且 pickup_time + delivery_duration ≤ delivery_time。
- 如果满足，则选择该订单，并更新 current_time = pickup_time + delivery_duration。
统计最多订单数。

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

bool compareOrders(const vector<int>& a, const vector<int>& b) 
{
    return a[1] < b[1]; 
}

int maxDeliveries(vector<vector<int>>& orders, int delivery_duration) 
{
    if (orders.empty()) return 0;

    sort(orders.begin(), orders.end(), compareOrders);

    int count = 0;
    int current_time = 0;

    for (const auto& order : orders) 
    {
        int pickup_time = order[0];
        int delivery_time = order[1];

        if (pickup_time >= current_time &&
            pickup_time + delivery_duration <= delivery_time) 
        {
            count++;
            cout << "送单时间: " << pickup_time << " - " << delivery_time << endl;
            current_time = pickup_time + delivery_duration;
        }
    }

    return count;
}

关于快递小哥送餐的题目还可以进行变种和扩展:

多单携带：若外卖小哥一次可携带 k 单，需结合优先队列（堆）优化。
动态送餐时间：不同订单的 delivery_duration 不同，需调整排序策略。
路径规划：结合最短路径算法（如 Dijkstra）优化送单顺序。

解决方案：最短路径 - 迪杰斯特拉（Dijkstra）算法

3. 贪心算法的局限性

虽然贪心算法在很多问题上简单高效，但它存在一定的局限性，并非所有问题都适用，具体有以下几点：

无法保证全局最优解

贪心算法仅考虑局部最优，每一步都做出当前看起来最好的选择，而不考虑这种选择对后续步骤以及整个问题的影响。这使得它在很多情况下得到的只是局部最优解，而不是全局最优解。

示例：在 0 - 1 背包问题中，有一个容量为 5 的背包，有 3 个物品，分别是物品 A（重量 3，价值 6）、物品 B（重量 2，价值 5）、物品 C（重量 2，价值 5）。若采用贪心算法，按单位重量价值（价值/重量）来选择，物品 A 的单位重量价值为 2，物品 B 和 C 的单位重量价值为 2.5。贪心算法会先选择物品 A，此时背包剩余容量为 2，无法再装下其他物品，总价值为 6。但实际上选择物品 B 和 C 能使背包总价值达到 10，这表明贪心算法得到的不是全局最优解。
缺乏回溯机制

贪心算法一旦做出选择，就不会再回头修改之前的决策。当问题的最优解依赖于对前面步骤的调整时，贪心算法就无法找到最优解。

示例：在旅行商问题（TSP）中，要求一个旅行商从某个城市出发，经过所有给定的城市且每个城市仅经过一次，最后回到出发城市，求最短的旅行路线。如果使用贪心算法，每次都选择距离当前城市最近的未访问城市，当到达某个城市后发现后续路线会导致整体路线变长，由于贪心算法没有回溯机制，无法回到之前的步骤重新选择，最终可能得到一个次优解。
对问题的要求苛刻
贪心算法的正确性依赖于问题本身具有贪心选择性质和最优子结构性质。贪心选择性质是指问题的全局最优解可以通过一系列局部最优选择得到；最优子结构性质是指问题的最优解包含其子问题的最优解。很多问题并不满足这两个性质，因此不能使用贪心算法。

在以下三种特定情形下，贪心算法往往难以得出令人满意的结果，甚至可能与全局最优解背道而驰：

无贪心选择性质：若全局最优解无法由一系列局部最优选择达成，贪心算法失效。
无最优子结构性质：当问题最优解不包含子问题最优解时，贪心算法不能得出正确结果。
决策相互影响：问题决策间存在复杂相互影响，一个决策影响后续可行性与最优性，贪心算法难以适用。