貪心算法之活動選擇問題

1. 前言

本節(jié)內容是貪心算法系列之一：活動選擇問題，主要講解了什么是活動選擇問題，如何利用貪心算法解決活動選擇問題，給出了活動選擇問題的實現(xiàn)偽代碼并進行分析，并用 java 語言進行了偽代碼實現(xiàn)，幫助大家通過活動選擇問題更好的理解貪心算法思想的應用。

2. 什么是活動選擇問題？

假設我們現(xiàn)在有一個 n 個活動的集合 S={a₁, a₂, a₃, …a_n}，這些活動需要使用相同一個資源，但是這個資源在某一個時刻只能被一個活動使用，并且每一個活動 a_i 都有一個開始時間 s_i 和結束時間 f_i ，其中 s_i < f_i ，并且開始時間和結束時間都在可以選擇的活動時間范圍內。這里，如果某個活動 a_i 被選中，則我們可以說活動 a_i 發(fā)生在半開時間區(qū)間 [ s_i，f_i ) 內，如果兩個活動 a_i 和 a_j 滿足 [ s_i, f_i ) 和 [ s_j, f_j ) 不重疊，則稱它們是兼容的。也就是說，若 s_i >= f_j 或者 s_j >= f_i , 則稱 a_i 和 a_j 是相互兼容的，在活動選擇問題中，我們希望選出一個最大兼容活動集。

我們考慮現(xiàn)實生活中的一個活動選擇問題實例，比如學校里面有一個大的階梯教室，可以用來上公開課。這里這個階梯教室就相當于是一個資源，不同的公開課，比如數(shù)學課、語文課、英語課等等，這就是一個個活動，并且每節(jié)課都有一個開始時間和結束時間，活動選擇問題就要求我們選擇出所有的可以在階梯教室中安排的課程，保證選出的課程集合是一個最大的兼容活動集。

接下來，就讓我們看看如何利用貪心算法解決活動選擇問題。

3. 貪心算法求解活動選擇問題

首先，我們假設活動以及按照結束時間的單調遞增的順序排序好，滿足： f₁ <= f₂ <= … <= f_i <= … f_n，考慮的活動集合如下：

回顧一下前一節(jié)我們在貪心算法介紹中提到的，能夠應用貪心算法求解的問題需要滿足兩個條件：最優(yōu)子結構和貪心選擇，接下來，我們就具體來看看在活動選擇問題中的最優(yōu)子結構和貪心選擇分別是什么。

3.1 最優(yōu)子結構

我們假設 S_ij 表示在 a_i 結束之后開始，并且在 a_j 開始之前結束的那些活動的集合。我們希望求得 S_ij 的一個最大的相互兼容的活動子集，我們假定 A_ij 就是這樣的一個子集，且其中包含活動 a_k 。由于最優(yōu)解包含活動 a_k ，我們得到兩個子問題：尋找 S_ik 中的兼容活動（在 a_i 結束之后開始且 a_k 開始之前結束的那些活動）以及尋找 S_kj 中的兼容活動（在 a_k 結束之后開始且 a_j 開始之前結束的那些活動)。

如上所述，我們假設 c [i, j] 表示集合 S_ij 的最優(yōu)解的大小，則可以按照這種方式去刻畫活動選擇問題的最優(yōu)子結構: c [i, j] = c [i, k] + c [k, j] + 1; 當然，如果我們不知道 S_ij 的最優(yōu)解包含活動 a_k ，就需要考察 S_ij 中所有活動，尋找哪個活動可以獲得最優(yōu)解，最終結果如下：

3.2 貪心選擇

假如我們無需求解所有的子問題就可以選擇出一個活動加入到最優(yōu)解，這樣可以使得我們省去遞歸考察所有選擇的過程。所以在活動選擇問題中，我們只需要考慮一種選擇：貪心選擇。

對于活動選擇問題，什么是貪心選擇？直觀上說，我們應該選擇一個這樣的活動，選擇它之后剩下的資源可以被盡量多的其他活動選擇占用。所以，在這個活動選擇問題中，我們選擇最早結束的活動，這樣剩下來的時間最多，剩下的資源可以供它之后盡量多的活動使用。

3.3 迭代貪心算法

按照上面分析的最優(yōu)子結構和貪心選擇方法，我們可以用迭代的方法去求解活動選擇問題，相關偽代碼如下：

GreedyActivitySelect(a,s,f):
    //定義活動總數(shù)
	n = s.length
    //按照貪心策略，首先選中第一個結束的活動
    A = {a[i]}
    //記錄當前選中的活動
    k = 1
    //for循環(huán)遍歷，按照貪心策略選擇活動
    for i=2 to n{
        if s[i] >= f[k]{
            A = A.add(a[i])
            k = i
        }
    }

其中，算法的輸入是活動選擇集合 a，活動選擇問題的開始時間 s 和結束時間 f ，并且已經(jīng)按照結束時間依次遞增的順序排序好。算法會將選擇的活動存入集合 A，最后返回集合 A 作為最終選擇的活動集合。

4.JAVA 代碼實現(xiàn)

在說明求解鋼條切割問題的整個過程之后，接下來，我們看看如何用 java 代碼實現(xiàn)鋼條切割問題的求解。

import java.util.ArrayList;
import java.util.List;

public class ActivitySelect {

    public static void main(String args[]){
        //活動集合a
        int a[] = {1,2,3,4,5,6,7,8,9,10,11};
        //活動開始時間集合s
        int s[] ={1,3,0,5,3,5,6,8,8,2,12};
        //活動結束集合f
        int f[] ={4,5,6,7,9,9,10,11,12,14,16};
        //活動選擇存放集合A
        List<Integer> A =  new ArrayList<>();

        int n = s.length;
        A.add(a[0]);
        int k =0;

        //遍歷選擇活動
        for (int i=1; i<n; i++){
            if(s[i] >= f[k]){
                A.add(a[i]);
                k = i;
            }
        }

        System.out.println("活動選擇問題的選擇活動結果為：");
        System.out.println(A);

    }
}

運行結果如下：

活動選擇問題的選擇活動結果為：
[1, 4, 8, 11]

代碼中第 7 行至第 14 行分別初始化活動和對應的開始時間、結束時間以及活動選擇過程中存放選擇的活動集合，代碼的第 16 至 18 行對應著開始的活動選擇初始化工作，因為 java 數(shù)組的下標從 0 開始，所以這里面我們第一個選擇的活動為 a [0]，而不是偽代碼中的 a [1]。代碼的第 20 行至 26 行 for 循環(huán)遍歷活動選擇，按照貪心選擇的方法選擇對應的活動，放入最終的結果集 A 中 ，代碼的 28 行 29 行輸出相關的活動選擇結果。

5. 小結

本節(jié)主要學習了利用貪心算法處理活動選擇問題，學習本節(jié)課程掌握貪心算法解決活動選擇問題的流程，知道貪心算法在解決問題時是如何考慮最優(yōu)子結構及尋找貪心選擇，并且可以自己用代碼實現(xiàn)活動選擇問題的求解。在學習完本節(jié)課程之后，我們通過活動選擇問題這一實例介紹了貪心算法的實際應用，幫助大家可以更好地理解貪心算法。