Blog·Tanky WooABOUTRSS

《算法导论》学习总结 — 22.第16章 贪心算法(2) 案例分析之活动选择问题

08 Jun 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

建议先看看前言:http://www.wutianqi.com/?p=2298

连载总目录:http://www.wutianqi.com/?p=2403

题目就不贴了,看书~~~

这个问题算是贪心算法中很经典的一道题目了。

按照书上所说,定义以下关系:

16_5

即:

16_6 (图有点丑~~~)

如果按照DP来做,可以找到以下关系:

16_7

不过,看看定理16.1(这个有必要自己仔细看看!)

它证明了为何这里可以用贪心。

Tanky Woo 标签: Tanky Woo贪心算法算法导论

(其实贪心这块和DP一样,很难说清楚,看多了,做多了,你就知道为何这个问题可以用DP,这个问题可以用贪心。。。)

下面贴出此题的代码:

#include 
#include 
using namespace std;

typedef struct Act{
    int s;   // start time
    int f;   // final time
}Act;

Act arr[100];
Act temp[100];
int n;

bool cmp(Act a, Act b)
{
    return a.f < b.f;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    cout << "输入活动个数: ";
    cin >> n;
    cout << "输入" << n << "个活动的开始和结束时间:" << endl;
    for(int i=0; i> arr[i].s >> arr[i].f;
    sort(arr, arr+n, cmp);
    int k = 0;


    temp[k] = arr[0];
    for(int i=1; i= temp[k].f)
            temp[++k] = arr[i];


    cout << "选择的活动: " << endl;
    for(int i=0; i<=k; ++i)
        cout << temp[i].s << " " << temp[i].f << endl;
    return 0;
}

结果如图:

16_8