贪心算法

• 1. 学习内容
  • 1.1 参考
  • 1.2 算法简介
• 2. 部分背包问题（Fractional Knapsack）
  • 2.1 示例问题描述
  • 2.2 示例问题分析
  • 2.3 编程练习
• 3. 最长事件序列（区间不重合）（Activity Selection Problem）
  • 3.1 示例问题描述
  • 3.2 示例问题分析
  • 3.3 编程
• 4. 最小区间覆盖（区间重合）
  • 4.1 示例问题描述
  • 4.2 示例解题过程
  • 4.3 编程练习
• 5. 阅读题
• 6. 补充阅读

1. 学习内容

1.1 参考

1. 《程序设计基础》第13章

1.2 算法简介

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。

2. 部分背包问题（Fractional Knapsack）

2.1 示例问题描述

有一个背包，背包容量是 M =150，有7个物品，物品可以分割成任意大小，要求尽可能让装入背包中的物品总价值最大，但不能超过总容量

物品	A	B	C	D	E	F	G
重量	35	30	60	50	40	10	25
价值	10	40	30	50	35	40	30

2.2 示例问题分析

选择性价比最高的，即算出单位价值，并按从大到小排序，依次放入背包，超重就不放，没超就继续放入，直到判断完所有物品

2.3 编程练习

1. 装船问题

3. 最长事件序列（区间不重合）（Activity Selection Problem）

3.1 示例问题描述

X轴上有N条线段，每条线段有1个起点S和终点E。最多能够选出多少条互不重叠的线段。（注：起点或终点重叠，不算重叠）。例如：[1 5][2 3][3 6]，可以选[2 3][3 6]，这2条线段互不重叠。

3.2 示例问题分析

以终点排序，最先结束就可以更早的开始，这样就可以选择更多的线段。

3.3 编程

1. 最长事件序列
2. 电影节

4. 最小区间覆盖（区间重合）

4.1 示例问题描述

给定一个长度为m的区间，再给出n条线段的起点和终点（注意这里是闭区间），求最少使用多少条线段可以将整个区间完全覆盖。

样例：区间长度8，可选的覆盖线段[2,6],[1,4],[3,6],[3,7],[6,8],[2,4],[3,5]

4.2 示例解题过程

1. 将每一个区间按照左端点递增顺序排列。样例排完序后为[1,4]，[2,4]，[2,6]，[3,5]，[3,6]，[3,7]，[6,8]
2. 设置变量
   • last 表示当前已经覆盖到的区域的最右边距离。
   • curr_max 表示在剩下的线段中找到的所有左端点小于等于当前已经覆盖到的区域的右端点的线段中，不断更新最右边的距离
3. 重复以上过程 直到区间全部覆盖 否则 区间不能全部覆盖

样例的具体过程:

1. 第一步加入[1,4] ，那么下一步能够选择的有[2,6]，[3,5]，[3,6]，[3,7]，由于7最大
2. 所以下一步选择[3,7]，最后一步只能选择[6,8]，这个时候刚好达到了8退出，所选区间为3

4.3 编程练习

1. Cleaning Shifts

参考代码实现：

#include <iostream>   //cin, cout
#include <algorithm>  //sort
#include <cmath>      //max
#include <stdio.h>    //scanf
using namespace std;

struct interval //区间
{
    int start;
    int end;
} cows[25000];

bool cmp(interval a, interval b)
{
    return a.start < b.start;
}

int main()
{
    int N, T;
    cin >> N >> T;

    //For huge input data, use scanf() instead of cin to read data to avoid time limit exceed.
    for (int i = 0; i < N; i++)
    {
        scanf("%d %d", &cows[i].start, &cows[i].end);
    }

    //直接使用c++中的算法库排序
    sort(cows, cows + N, cmp);

    int last = 0; //上一个结束
    int num = 0;  //总数量
    int q = -1;   //遍历。
    while (last < T)
    {
        int curr_max = last;
        //注意点：区间可以是断的，比如[1,3] [4,7] 只要后一个start<=前一个end+1就行
        while (q + 1 < N && cows[q + 1].start <= last + 1)
        {
            q++;
            curr_max = max(curr_max, cows[q].end);
        }

        if (curr_max == last) //没有递增
            break;

        num++; //当前有递增。
        last = curr_max;
    }

    if (last < T)
        num = -1;
    
    cout << num << endl;
}

5. 阅读题

1、

【CSP 2020 入门组第一轮 q20】【完善程序】（最小区间覆盖）给出 n 个区间，第 i 个区间的左右端点是 $[a_i,b_i]$。现在要在这些区间中选出若干个，使得区间 [0, m] 被所选区间的并覆盖（即每一个 0≤i≤m 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。

输入第一行包含两个整数 n 和 m （$1\le n \le 5000,1\le m \le 10^9$） 接下来 n 行，每行两个整数 $a_i$，$b_i$ （$0\le a_i,b_i \le m$）。

提示：使用贪心法解决这个问题。先用 $O(n^2)$ 的时间复杂度排序，然后贪心选择这些区间。

试补全程序。

   #include <iostream>

   using namespace std;

   const int MAXN = 5000;
   int n, m;
   struct segment { int a, b; } A[MAXN];

   void sort() // 排序
   {
     for (int i = 0; i < n; i++)
       for (int j = 1; j < n; j++)
         if (①)
         {
           segment t = A[j];
           ②
         }
   }

   int main()
   {
     cin >> n >> m;
     for (int i = 0; i < n; i++)
       cin >> A[i].a >> A[i]・b;
     sort();
     int p = 1;
     for (int i = 1; i < n; i++)
       if (③)
         A[p++] = A[i];
     n = p;
     int ans =0, r = 0;
     int q = 0;
     while (r < m)
     {
       while (④)
         q++;
       ⑤;
       ans++;
     }
     cout << ans << endl;
     return 0;
   }

1）①处应填（ ）
A. A[j].b>A[j-1].b   B. A[j].a<A[j-1].a  
C. A[j].a>A[j-1].a   D. A[j].b<A[j-1].b  

2）②处应填（ ）
A. A[j+1]=A[j];A[j]=t;   B. A[j-1]=A[j];A[j]=t;  
C. A[j]=A[j+1];A[j+1]=t;   D. A[j]=A[j-1];A[j-1]=t;  

3）③处应填（ ）
A. A[i].b>A[p-1].b   B. A[i].b<A[i-1].b  
C. A[i].b>A[i-1].b   D. A[i].b<A[p-1].b  

4）④处应填（ ）
A. q+1<n&&A[q+1].a<=r   B. q+1<n&&A[q+1].b<=r  
C. q<n&&A[q].a<=r   D. q<n&&A[q].b<=r  

5）⑤处应填（ ）
A. r=max(r,A[q+1].b)   B. r=max(r,A[q].b)  
C. r=max(r,A[q+1].a)   D. q++  

6. 补充阅读

1. 贪心算法2