算法分析与设计-会场安排问题（贪心）（通俗易懂，附源码和图解，含贪心选择性质和最优子结构性质的证明）（c++)-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法分析与设计-会场安排问题（贪心）（通俗易懂，附源码和图解，含贪心选择性质和最优子结构性质的证明）（c++)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

4-1 会场安排问题

（一）题目

问题描述

假设在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。（这个问题实际上是著名的图着色问题。若将每个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点有着不同颜色的最小着色数，相当于要找的最少会场数。）

算法设计

对于给定的 $n$ 个待安排活动，计算使用最少会场的时间。

数据输入

由文件input.txt提供输入数据。第1行中有一个整数 $n$ ，表示有 $n$ 个待安排的活动。接下来的 $n$ 行中，每行有2个正整数，分别表示 $n$ 个待安排的活动的开始时间和结束时间。时间以0点开始的分钟计。

结果输出

将计算的最少会场数输出到文件output.txt。

（二）解答

方法思路

会场安排问题可以用贪心算法求解，采用结束时间最早的会场作为贪心选择

算法具体描述：

1）用数组s和f分别存储各活动的开始时间和结束时间，将s按非递减排序，该次序为各活动选择会场的次序；将f按非递减排序, 由于会场的结束时间由活动的结束时间决定，排序后的数组也是会场的结束时间点。

2）先为最早开始的活动开辟一个会场，此时会场的最早结束时间为该活动的结束时间，然后遍历剩下的活动，对于每个活动，判断当前最早结束的会场内是否仍有活动（即会场的最早结束时间大于该活动的开始时间），如果有，开辟一个新会场；如果没有，说明当前最早结束的会场能容纳当前的活动，更新会场的结束时间点，保证最早结束的会场最先开始下一个活动。

算法正确性证明：

1）贪心选择性质的证明

优解包含贪心选择的证明可用反证法，证明如下：

假设最优解不含贪心选择，即最优解 $A$ 的某个活动 $a$ 所选择的会场 $r ’$ 不是结束时间最早的会场 $r$ ，由于 $r$ 的结束时间小于 $r ’$ ， $a$ 能在 $r$ 中进行，说明 $a$ 必定能在 $r$ 中进行，因此用 $r$ 代替 $r ’$ 的结果 $(A-\{r'\})\cup\{r\}$ 仍是一个最优解，即最优解包含贪心选择，与假设矛盾。

2）最优子结构性质的证明

若 $A$ 是原问题 $E$ 的最优解，会场 $r_1$ 安排的活动集合为 $e$ ，则 $A'=A-\{r_1\}$ 是子问题 $E^{'} = E - e$ 的最优解，该命题的证明可用反证法，证明如下：

假设 $B^{'}$ 是子问题 $E^{'}$ 的更优解， $B^{'}$ 比 $A^{'}$ 所需的会场数更少，由于 $E^{'}$ 与 $e$ 不相容，新开辟一个会场 $r$ 容纳活动集合 $e$ 对 $B^{'}$ 无影响，那么 $B'\cup\{r\}$ 是原问题的更优解，与假设矛盾。

综上，会场安排问题可用贪心算法求解，且将结束时间最早的会场为贪心选择能得到最优解。

举例

设有4个活动，每个活动的开始和结束时间分别为{1, 6}, {4, 8}, {9, 10}, {7, 18}
算法分析与设计-会场安排问题（贪心）（通俗易懂，附源码和图解，含贪心选择性质和最优子结构性质的证明）（c++)
总共需要2个会场

源代码

#include <cstdio>
#include <iostream>
#include<fstream>
#include <algorithm>

using namespace std;

int main()
{
    int n; //活动个数
    int s[100]; //各活动开始时间
    int f[100]; //各活动结束时间
    int i, j; //i，j分别指向开始时间和结束时间
    int ans; //结果

    //文件输入
    ifstream ifs;
    ifs.open("G:\\algorithm\\data\\4_1_input.txt", ios::in);
    ifs>>n;
    for (int i = 1; i <= n; ++i)
    {
        ifs>>s[i]>>f[i];
    }
    ifs.close();

    //排序
    sort(s + 1, s + n + 1); //将各活动的开始时间按非递减排序，排序后的数组为各活动选择会场的次序
    sort(f + 1, f + n + 1); //将各活动的结束时间按非递减排序，由于会场的结束时间由活动的结束时间决定，排序后的数组也是会场的结束时间点
    
    //为最早开始的活动开辟一个会场，此时会场的最早结束时间为该活动的结束时间
    j = 1;
    ans = 1;
    
    //遍历剩下的活动
    for (int i = 2; i <= n; ++i)
    {
        //判断当前最早结束的会场内是否仍有活动
        //如果有，开辟一个新会场
        if (f[j] > s[i])
        {
            ans++;
        }
        //如果没有，说明当前最早结束的会场能容纳当前的活动，更新会场的结束时间点，保证最早结束的会场最先开始下一个活动
        else
        {
            j++;
        }
    }

    //文件输出
    ofstream ofs;
    ofs.open("G:\\algorithm\\data\\4_1output.txt", ios::out);
    ofs<<ans<<endl;
    ofs.close();
}