貪心算法

貪心算法基本思路

image.png

貪心算法的基本思想

?貪心算法的特點是每個階段所作的選擇都是局部最優(yōu)的，它期望通過所作的局部最優(yōu)選擇產(chǎn)生出一個全局最優(yōu)解。

貪心與動態(tài)規(guī)劃：與動態(tài)規(guī)劃不同的是，貪心是鼠目寸光；動態(tài)規(guī)劃是統(tǒng)攬全局。

–動態(tài)規(guī)劃：每個階段產(chǎn)生的都是全局最優(yōu)解

?第i階段的“全局”： 問題空間為(a1, … , ai)

?第i階段的“全局最優(yōu)解”：問題空間為 (a1, … , ai)時的最優(yōu)解

–貪心：每個階段產(chǎn)生的都是局部最優(yōu)解

?第i階段的“局部”：問題空間為按照貪心策略中的優(yōu)先級排好序的第i個輸入ai

?第i階段的“局部最優(yōu)解”： ai

貪心算法的基本要素

?貪心選擇性質(zhì)：所求問題的全局最優(yōu)解可以通過一系列局部最優(yōu)的選擇（即貪心選擇）來達(dá)到。

–這是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。

?最優(yōu)子結(jié)構(gòu)性質(zhì)：當(dāng)原問題的最優(yōu)解包含子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征

活動安排——貪心算法

?要求高效地安排一系列爭用某一公共資源（例如會議室）的活動（使盡可能多的活動能兼容使用公共資源）。

–設(shè)有n個活動的集合E={e1,e2…en}，其中每個活動都要求使用同一資源，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束時間fi，且si<fi。如果選擇了活動i，則它在半開時間區(qū)間[si,fi)內(nèi)占用資源。

–若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱ei和ej是相容的。也就是說，當(dāng)si≥fj或sj≥fi時，活動i和活動j相容。

?活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合。

image.png

image.png

image.png

// 貪心算法-活動安排.cpp : 此文件包含 "main" 函數(shù)。程序執(zhí)行將在此處開始并結(jié)束。
//

#include <iostream>
#include <algorithm>

using namespace std;

struct activity
{
    int s;
    int f;
    int index;
};

bool cmp(activity a,activity b)
{
    if (a.f <= b.f)
        return true;
    else
        return false;
}

void GreedySelector(int n, activity a[], bool b[])
{
    b[1] = true;
    int pre = 1;
    for (int i = 2;i <= n;i++)
    {
        if (a[i].s >= a[pre].f)
        {
            b[i] = 1;
            pre = i;
        }
    }
}


int main()
{
    int n;
    cin >> n;
    activity a[1000];
    bool b[1000];
    memset(b, false, sizeof(b));
    for (int i = 1;i <= n;i++)
    {
        cin >> a[i].s >> a[i].f;
        a[i].index = i;
    }
    sort(a, a + n + 1, cmp);
    GreedySelector(n, a, b);
    for (int i = 0;i <= n;i++)
    {
        if (b[i])
            cout << a[i].index << " " << endl;
    }
    return 0;
}