贪心算法___2023-08-08

目录

定义

在某一个标准下，优先考虑最满足标准的样本，最后考虑最不满足标准的样本，最终得到一个答案的算法，叫作贪心算法。
也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。

案例分析

例1: 安排会议

“安排会议”是一道经典的贪心算法
题目的第一问是：给定N个会议的开始时间和结束时间，求最多能安排多少个会议
此处给出第一问的代码

#include <bits/stdc++.h>
using namespace std;

struct meeting
{
    int start;
    int end;
    int id;
};

int getMaxCount(vector<meeting *> meetings)
{
    sort(meetings.begin(), meetings.end(), [](meeting *a, meeting *b) {
        return a->end < b->end;
    });
    int count = 1;
    int curTime = meetings[0]->end;
    for (int i = 1; i < meetings.size(); i++)
    {
        if (meetings[i]->start > curTime)
        {
            count++;
            curTime = meetings[i]->end;
        }
    }
    return count;
}

int main(){
    int M;
    cin >> M;
    vector<meeting*> meetings;
    for (int i=0;i<M;i++){
        int start, end;
        cin >> start >> end;
        meeting *m = new meeting();
        m->start = start;
        m->end = end;
        m->id = i+1;
        meetings.push_back(m);
    }
    int count = getMaxCount(meetings);
    cout << count << endl;
}

这里”贪心”的标准是：优先安排结束时间早的会议，因为这样可以给后面的会议留下更多的时间
但是显然这样的论述是不严谨的，因为我们并没有用数学方法证明这样的安排方式一定是最优的
而证明会是极其复杂的, 因此要用实验的方式去试, 而不是反复纠结

例2: 切金条

题目

一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金条，不管切成长度多大的两半，都要花费20个铜板。
一群人想整分整块金条，怎么分最省铜板？
例如，给定数组{10,20,30}，代表一共三个人，整块金条长度为10 20 30=60。金条要分成10,20,30三个部分。如果先把长度60的金条分成10和50，花费60；再把长度50的金条分成20和30，花费50；一共花费110铜板。
但是如果先把长度60的金条分成30和30，花费60；再把长度30金条分成10和20，花费30；一共花费90铜板。
输入一个数组，返回分割的最小代价。

分析

经典的哈夫曼编码问题，贪心策略是：每次都把最小的两个数加起来，然后再把这个和加到一起，直到最后只剩下一个数

流程如下:
+ 先做成小根堆
+ 每次弹出两个数, 加起来
+ 将加和的结果扔到小根堆中
+ 直到小根堆中只剩下一个数, 返回这个数

代码

int lessMoneyCutGoldBar(vector<int> nums)
{
    priority_queue<int, vector<int>, greater<int>> heap;
    for (auto num : nums)
    {
        heap.push(num);
    }
    int ans = 0;
    int cur = 0;
    while (heap.size() > 1)
    {
        cur = heap.top();
        heap.pop();
        cur += heap.top();
        heap.pop();
        ans += cur;
        heap.push(cur);
    }
    return ans;
}

例3: 做项目

题目

• 输入：
  1. 正数数组costs
  2. 正数数组profits
  3. 正数k
  4. 正数m
• 含义：
  • costs[i]表示i号项目的花费
  • profits[i]表示i号项目在扣除花费之后还能挣到的钱（利润）
  • k表示你只能串行的最多做k个项目
  • m表示你初始的资金
• 说明：
  你每做完一个项目，马上获得的收益，可以支持你去做下一个项目。
  每个项目只能做一次，不能重复
• 输出：
  你最后获得的最大钱数。

分析

• 用一个小根堆存储所有的项目，按照花费排序(锁住的项目)
• 用一个大根堆存储所有的项目，按照利润排序(可以做的项目)
• 每次从小根堆中弹出所有花费小于等于当前资金的项目，放到大根堆中
• 从大根堆中弹出一个项目，做完这个项目，资金增加，继续循环

代码

#include <bits/stdc++.h>
using namespace std;

struct Project
{
    int cost;
    int profit;

    Project(int cost, int profit)
    {
        this->cost = cost;
        this->profit = profit;
    }
};

struct costCmp
{
    bool operator()(Project *a, Project *b)
    {
        return a->cost > b->cost; // 小根堆
    }
};

struct profitCmp
{
    bool operator()(Project *a, Project *b)
    {
        return a->profit < b->profit; // 大根堆
    }
};

class Solution
{
public:
    int k, m;
    vector<Project *> projects;
    // 根据cost的小根堆, 使用自定义比较函数
    priority_queue<Project *, vector<Project *>, costCmp> costPQ;
    // 根据profit的大根堆, 使用自定义比较函数
    priority_queue<Project *, vector<Project *>, profitCmp> profitPQ;
    int insert(int cost, int profit)
    {
        Project *p = new Project(cost, profit);
        costPQ.push(p);
    }
    void unlock()
    {
        while (!costPQ.empty() && costPQ.top()->cost <= m)
        {
            profitPQ.push(costPQ.top());
            costPQ.pop();
        }
    }
    int getMaxProfit()
    {
        unlock();
        while (k-- && !profitPQ.empty())
        {
            m += profitPQ.top()->profit;
            profitPQ.pop();
            unlock();
        }
        return m;
    }
};

int main()
{
    Solution s;
    s.k = 3;
    s.m = 1;
    s.insert(1, 2);
    s.insert(2, 3);
    s.insert(3, 4);
    s.insert(4, 5);
    s.insert(5, 6);
    cout << "max profit:" << endl;
    cout << s.getMaxProfit() << endl;
}

优先级队列的比较器有点反逻辑, 需要注意比较器的写法

笔试注意事项

1. 实现一个不依靠贪心策略的解法X, 可以用最暴力的尝试
2. 脑补出贪心策略A、贪心策略B、贪心策略C.
3. 用解法X和对数器，去验证每一个贪心策略，用实验的方式得知哪个贪心策略正确
4. 不要去纠结贪心策略的证明