貪心算法之活動(dòng)選擇問題

1. 前言

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

2. 什么是活動(dòng)選擇問題？

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

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

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

3. 貪心算法求解活動(dòng)選擇問題

首先，我們假設(shè)活動(dòng)以及按照結(jié)束時(shí)間的單調(diào)遞增的順序排序好，滿足： f₁ <= f₂ <= … <= f_i <= … f_n，考慮的活動(dòng)集合如下：

回顧一下前一節(jié)我們?cè)谪澬乃惴ń榻B中提到的，能夠應(yīng)用貪心算法求解的問題需要滿足兩個(gè)條件：最優(yōu)子結(jié)構(gòu)和貪心選擇，接下來，我們就具體來看看在活動(dòng)選擇問題中的最優(yōu)子結(jié)構(gòu)和貪心選擇分別是什么。

3.1 最優(yōu)子結(jié)構(gòu)

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

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

3.2 貪心選擇

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

對(duì)于活動(dòng)選擇問題，什么是貪心選擇？直觀上說，我們應(yīng)該選擇一個(gè)這樣的活動(dòng)，選擇它之后剩下的資源可以被盡量多的其他活動(dòng)選擇占用。所以，在這個(gè)活動(dòng)選擇問題中，我們選擇最早結(jié)束的活動(dòng)，這樣剩下來的時(shí)間最多，剩下的資源可以供它之后盡量多的活動(dòng)使用。

3.3 迭代貪心算法

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

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

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

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

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

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

public class ActivitySelect {

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

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

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

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

    }
}

運(yùn)行結(jié)果如下：

活動(dòng)選擇問題的選擇活動(dòng)結(jié)果為：
[1, 4, 8, 11]

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

5. 小結(jié)

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