贪心算法解题方法介绍+实操案例——会场安排与月饼售卖问题解析

从贪心算法到实操案例——会场安排与月饼售卖问题解析

前言

贪心算法是一种通过选择局部最优解来尝试构建全局最优解的算法。它简单高效，适用于许多优化问题。本文将详细介绍贪心算法的一般解题步骤，并通过两个实例——月饼售卖问题和会场安排问题——演示如何将贪心思想转化为实际代码。

一、贪心算法的解题步骤

要正确运用贪心算法，通常需要遵循以下步骤：

1. 问题建模：将问题转化为一个需要优化的模型。

   • 找到决策点，即每一步需要做出选择的地方。
   • 定义选择的局部最优标准。

2. 贪心选择性质：判断每次选择的局部最优解是否能够导向全局最优解。如果不能，贪心算法不适用。

3. 算法设计与验证：

   • 按照局部最优标准设计决策逻辑。
   • 用实例验证贪心选择的正确性。

4. 代码实现与优化：

   • 实现算法，通常包括排序和迭代。
   • 根据实际场景优化代码，例如选择合适的数据结构（如数组或堆）。

二、案例解析

1. 月饼售卖问题

问题描述

我们需要选择出售哪些月饼以及出售多少，以获得最大收益。可以按库存和售价计算单位收益（单价），每次优先选择单位收益最高的月饼出售。

贪心解法

1. 局部最优选择：每次选择单位收益最高的月饼。
2. 算法设计：
   • 计算每种月饼的单位收益。
   • 按单位收益降序排序。
   • 按需出售月饼，直到满足市场需求或所有库存耗尽。

C++实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

// 定义月饼的结构体
struct Mooncake {
    double stock, price, unit_price;
};

// 比较函数，按单位收益降序排序
bool compare(Mooncake a, Mooncake b) {
    return a.unit_price > b.unit_price;
}

int main() {
    int n;       // 月饼种类数
    double demand; // 市场最大需求量
    cin >> n >> demand;

    vector<Mooncake> mooncakes(n);

    // 输入库存和总售价
    for (int i = 0; i < n; i++) {
        cin >> mooncakes[i].stock;
    }
    for (int i = 0; i < n; i++) {
        cin >> mooncakes[i].price;
        mooncakes[i].unit_price = mooncakes[i].price / mooncakes[i].stock;
    }

    // 按单位收益降序排序
    sort(mooncakes.begin(), mooncakes.end(), compare);

    double max_profit = 0.0; // 最大收益

    // 贪心选择月饼
    for (int i = 0; i < n && demand > 0; i++) {
        if (mooncakes[i].stock <= demand) {
            max_profit += mooncakes[i].price; // 卖掉全部库存
            demand -= mooncakes[i].stock;
        } else {
            max_profit += mooncakes[i].unit_price * demand; // 部分出售
            demand = 0; // 需求满足
        }
    }

    // 输出结果，保留两位小数
    cout << fixed << setprecision(2) << max_profit << endl;

    return 0;
}

输入输出示例

输入：

3 20
18 15 10
75 72 45

输出：

94.50

2. 会场安排问题

问题描述

有一批需要安排的活动，每个活动有开始和结束时间。我们希望用尽可能少的会场安排所有活动。

贪心解法

1. 局部最优选择：每次选择最早结束的会场复用，避免时间冲突。
2. 算法设计：
   • 按开始时间排序活动。
   • 维护一个会场结束时间的数组或堆。
   • 遍历活动，检查是否有可以复用的会场，如果没有，则新增会场。

使用数组实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Activity {
    int start, end;
};

bool compare(Activity a, Activity b) {
    return a.start < b.start;
}

int minMeetingRooms(vector<Activity>& activities) {
    sort(activities.begin(), activities.end(), compare);

    vector<int> endTimes;
    for (auto& activity : activities) {
        bool assigned = false;
        for (int i = 0; i < endTimes.size(); i++) {
            if (endTimes[i] <= activity.start) {
                endTimes[i] = activity.end;
                assigned = true;
                break;
            }
        }
        if (!assigned) {
            endTimes.push_back(activity.end);
        }
    }
    return endTimes.size();
}

int main() {
    int k;
    cin >> k;
    vector<Activity> activities(k);
    for (int i = 0; i < k; i++) {
        cin >> activities[i].start >> activities[i].end;
    }
    cout << minMeetingRooms(activities) << endl;
    return 0;
}

使用最小堆实现

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Activity {
    int start, end;
};

bool compare(Activity a, Activity b) {
    return a.start < b.start;
}

int minMeetingRooms(vector<Activity>& activities) {
    sort(activities.begin(), activities.end(), compare);

    priority_queue<int, vector<int>, greater<int>> minHeap;
    for (auto& activity : activities) {
        if (!minHeap.empty() && minHeap.top() <= activity.start) {
            minHeap.pop();
        }
        minHeap.push(activity.end);
    }
    return minHeap.size();
}

int main() {
    int k;
    cin >> k;
    vector<Activity> activities(k);
    for (int i = 0; i < k; i++) {
        cin >> activities[i].start >> activities[i].end;
    }
    cout << minMeetingRooms(activities) << endl;
    return 0;
}

输入输出示例

输入：

5
1 23
12 28
25 35
27 80
36 50

输出：

3

三、总结

1. 贪心算法的核心：在每一步选择中，局部最优选择能保证全局最优解。
2. 适用场景：
   • 贪心算法适用于问题具有贪心选择性质和最优子结构。
3. 常用思路：
   • 排序问题中，贪心思想常通过排序和选择结合实现。
   • 数据结构选择（如数组、堆）能影响实现效率，应根据需求选择。

通过对月饼售卖问题和会场安排问题的分析，希望能帮助大家对贪心算法有了更加深入的理解和掌握！
如果对你有所帮助，欢迎点点免费的三连哦！