MyDocuments

Appearance

greedy ​

贪心算法 greedy algorithm

什么是贪心算法 ​

贪心算法(又称为贪婪算法),指在面临一个较大问题的时候,选择当前情况下看来是最好的选择.也是不从整体加以考虑,只显示局部最优解.

贪心算法不保证会得到最优解,但是在某些问题上贪心算法就是最优解.

参考问题 ​

1. 找零问题 ​

s

2. 拼接数字问题 ​

在 LeetCode 的 面试题45. 把数组排成最小的数 中

3. 活动选择问题 ​

区间覆盖

有N个活动,这些活动需要占用同一片场地,而场地同一时间只允许进行一个活动.

每个活动都有一个开始时间 S~i~ 和结束时间 F~i~ ,本题中均用正整数表示

请你计算该如何安排活动才能使举办的活动数量最多?

解答: 使用贪心算法尽可能进行最早结束的活动

C++ 代码实现

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

class tr2{
public:
    struct Action {
        int start;
        int end;
    };
    
    int MostActivities(vector<Action> activities) {
        vector<Action> AddAction;
        sort(activities.begin(), activities.end(), [&](const Action a,const Action b) {
            return a.end < b.end;
        });
        if (activities.empty()) {
            return AddAction.size();
        } else {
            AddAction.push_back(activities[0]);
        }
        for (size_t i = 1,ll = 0; i < activities.size(); i++) {
            if(AddAction.back().end <= activities[i].start) {
                AddAction.push_back(activities[i]);
            }
        }
        return AddAction.size();
    }
} S;

int main() {
    vector<tr2::Action> Activities{{1,4},{3,5},{0,6},{5,7},{3,9},{5,9},{6,10},{8,11},{8,12},{2,14},{12,16}};
    int a = S.MostActivities(Activities);
    cout << a;
    return 0;
}

分数背包 ​

分数最优解

数字拼接问题 ​

邻项对比法

贪心对应的三种做法 ​

邻项交换法 ​

将所有元素进行两两比较以求出最佳方案

分数最优解 ​

区间覆盖 ​

q

IAALAI