判斷題

能夠用貪心算法求解的問題一定能用動態(tài)規(guī)劃求解 --------F
貪心算法需要滿足兩個條件，貪心選擇性和最優(yōu)子結(jié)構(gòu)，動態(tài)規(guī)劃算法需要滿足最優(yōu)子結(jié)構(gòu)和重復(fù)子問題，滿足貪心算法兩要素的問題不一定滿足動態(tài)規(guī)劃算法的兩個要素。

問題一

設(shè)有n個正整數(shù)，將它們連接成一排，組成一個最大的多位整數(shù)。
例如：n=3時，3個整數(shù)13，312，343，連成的最大整數(shù)為34331213。
又如：n=4時，4個整數(shù)7，13，4，246，連成的最大整數(shù)為7424613。
輸入是n個正整數(shù)，輸出是這n個正整數(shù)連成的最大多位整數(shù)，要求用貪心法求解該問題。答案要求包含以下內(nèi)容：（1）證明問題具有貪心選擇性；（2）證明問題具有優(yōu)化子結(jié)構(gòu)；（3）寫出算法偽代碼并分析算法的時間復(fù)雜度。
貪心選擇性：每次選擇最高位最大的數(shù)字優(yōu)先輸出，如果最高位相同則比較次高位，同樣選擇數(shù)字較大的，如果是類似123，,1230這樣的情況，選擇位數(shù)較少的數(shù)字。
以最高位不同為例進行證明：
假設(shè)a1a2...aib1b1...bn?ia_1a_2...a_ib_1b_1...b_{n-i}a1a2...aib1b1...bn?i是最大多位數(shù)，且其最高位所在的數(shù)字a1a2...aia_1a_2...a_ia1a2...ai不是依據(jù)上述貪心思想選擇出來的，則一定有數(shù)字c1c2...cjc_1c_2...c_jc1c2...cj滿足c1>a1c_1>a_1c1>a1，下面證明以c1c2...cjc_1c_2...c_jc1c2...cj開頭的數(shù)字c1c2...cjd1d2...dn?jc_1c_2...c_jd_1d_2...d_{n -j}c1c2...cjd1d2...dn?j比a1a2...aib1b1...bn?ia_1a_2...a_ib_1b_1...b_{n-i}a1a2...aib1b1...bn?i大。
a1a2...aib1b1...bn?i<（a1+1）?10n?1a_1a_2...a_ib_1b_1...b_{n-i}<（a_1+ 1）*10^{n-1}a1a2...aib1b1...bn?i<（a1+1）?10n?1
c1c2...cjd1d2...dn?j≥c1?10n?1c_1c_2...c_jd_1d_2...d_{n -j}\geq c_1*10^{n-1}c1c2...cjd1d2...dn?j≥c1?10n?1
因為c1>a1c_1>a_1c1>a1所以c1?10n?1≥(a1+1)?10n?1c_1*10^{n-1}\geq (a_1+1)*10^{n-1}c1?10n?1≥(a1+1)?10n?1,進而得到c1c2...cjd1d2...dn?jc_1c_2...c_jd_1d_2...d_{n -j}c1c2...cjd1d2...dn?j比a1a2...aib1b1...bn?ia_1a_2...a_ib_1b_1...b_{n-i}a1a2...aib1b1...bn?i大，與 a1a2...aib1b1...bn?ia_1a_2...a_ib_1b_1...b_{n-i}a1a2...aib1b1...bn?i是最大的多位數(shù)矛盾。
最優(yōu)子結(jié)構(gòu)：復(fù)制-黏貼法容易證明。

bool campare(string i, string j){
    return (i+j) > (j+i);}sort(tmp.begin(), tmp.end(), campare);  // campare為假時交換i 和 j

平均時間復(fù)雜度O(nlgn)O(nlgn)O(nlgn)

問題二

存放于磁帶上文件需要順序訪問。故假設(shè)磁帶上依次存儲了n個長度分別是L[1],….,L[n]的文件，則訪問第k個文件需要順次訪問前K個文件（老師題目缺失） ?，F(xiàn)給定n個文件的長度L[1],….,L[n]，并假設(shè)每個文件被訪問的概率相等，試設(shè)計一個算法輸出這n個文件在磁帶上的存儲順序使得平均訪問代價最小。
答案要求包含以下內(nèi)容：（1）證明問題具有貪心選擇性；（2）證明問題具有優(yōu)化子結(jié)構(gòu)；（3）給出算法并分析算法的時間復(fù)雜度。
存儲方式：長度最短的存在最前面。

平均訪問長度為∑i=1np?Li=p?(n?L1+(n?1)?L2+...+Ln)\sum_{i = 1}^np*L_i=p*(n * L_1 + (n-1)*L_2+...+L_n)∑i=1np?Li=p?(n?L1+(n?1)?L2+...+Ln),p=1/np=1/np=1/n

1. 證明貪心選擇性：利用上述的平均訪問長度表達式即可證明。

2. 最優(yōu)子結(jié)構(gòu)：略。

3. 將長度排序即可。平均時間復(fù)雜度是O(nlgn）O(nlgn）O(nlgn）

題目三

G=(V, E)是一個具有n個頂點m條邊的連通圖，且可以假設(shè)邊的代價為正且各不相同，設(shè)，定義T的瓶頸邊是T中代價最大的邊，G的一個生成樹T是一棵最小瓶頸生成樹，如果不存在G的生成樹T’使得它具有代價更小的瓶頸邊。
問:(1)G的每棵最小瓶頸樹一定是G的一棵生成樹嗎？證明或者給出反例;
(2) G的每棵生成樹都是G的最小瓶頸樹嗎？證明或者給出反例。

1. 是。由最小瓶頸樹的定義可知G的最小瓶頸樹是G的生成樹。

2. 是。證明：l1<l2<l3...<lml1<l2<l3...<lml1<l2<l3...<lm,這m個數(shù)是G中m條邊的權(quán)值。最小生成樹中的邊是l1,l2,l3...ln?1l1,l2,l3...l{n-1}l1,l2,l3...ln?1，G的最小瓶頸樹中有(n-1)條邊,顯然在G中無法找到（n-1）條邊，并且這些邊中最大的權(quán)值小于ln?1ln-1ln?1。

題目四

給定n個自然數(shù)d1, d2, …, dn, 設(shè)計算法，在多項式時間確定是否存在一個無向圖G，使它的結(jié)點度數(shù)準確地就是d1, d2, …, dn， 要求G中在任意兩個結(jié)點之間至多有一條邊，且不存在一個結(jié)點到自身的邊。

d\\數(shù)組，保存規(guī)定的各點的度
sort（d）//將d數(shù)組按照數(shù)值從大到小排序for i = 1 to n
    end = d[i]
    for j = (i + 1) to min(n, i + end)
        if d[j] > 0 && d[i] > 0
            d[j]--
            d[i]--
        if d[i] == 0
            break
    if d[i] > 0 
        return false//表示不可以生成指定權(quán)值的圖return true

時間復(fù)雜度O(nlgn)O(nlgn)O(nlgn)

題目五

在一個操場上擺放著n堆石子，現(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選擇任意兩堆石子合并成新的一堆，并將新一堆石子數(shù)記為該次合并的得分。試設(shè)計貪心算法，計算出將n堆石子合并成一堆的最小得分和最大得分，寫出算法的偽代碼并分析算法的計算復(fù)雜性。（數(shù)組d記錄這n堆石子的石子數(shù)，下標范圍是0-(n-1)）
計算合并這n堆石子的最小得分，最大得分類似。（sum記錄合并這個石子堆的代價）
以計算最小得分為例：

1. 初始化sum為0

2. 將數(shù)組d按照從小到大的順序排序

3. 取出最小的兩個石子堆d[i],d[j],將d[i],d[j]從數(shù)組中刪除，將d[i]+d[j]加進d數(shù)組，sum加上d[i]+d[j],

4. 如果數(shù)組d大小是1，則返回sum，否則繼續(xù)第2步
   使用堆排序。

題目六

利用貪心法設(shè)計算法求解下述問題：
輸入：正整數(shù)集合S，正整數(shù)W
輸出：S的子集合S’，其中元素之和不小于W，且S’是滿足這個條件的子集合中包含元素數(shù)量最少的。
要求：(1) 闡明貪心思想 (2) 寫出偽代碼 (3) 證明算法正確性 (4) 分析算法時間復(fù)雜度

1. 按照從大到小的順序挑選S中的正整數(shù)。

2. 
   

S //表示正整數(shù)集合S'表示即將輸出的S的子集合sort(S)//表示將集合中的元素排序，排序之后假設(shè)按照從大到小的順序排序sum = 0while sum < W
    max = getMax(S)//表示得到S中最大的正整數(shù)
    delete(S, max)//表示將S中的數(shù)值是max的數(shù)字刪去一個
    add(S', max)//表示將max加進S'集合
    sum += maxreturn S'

1. 證明貪心選擇性和最優(yōu)子結(jié)構(gòu)即可。
   貪心選擇性：最優(yōu)解中一定包含S中現(xiàn)有正整數(shù)的最大值。
   假設(shè)S={s1,s2,s3...sn}S=\{s_1,s_2,s_3...s_n\}S={s1,s2,s3...sn}且滿足s1≤s2≤s3...≤sns_1\leq s_2\leq s_3...\leq s_ns1≤s2≤s3...≤sn,則最優(yōu)解S’中一定要包含sns_nsn.
   如果S′={a1,a2,a3,...an},a1≤a2≤...≤anS'=\{a_1,a_2,a_3,...a_n\},a1\leq a2\leq ...\leq a_nS′={a1,a2,a3,...an},a1≤a2≤...≤an是最優(yōu)解。且∑1nai=sum1≥W\sum_1^nai = sum_1\geq W∑1nai=sum1≥W,現(xiàn)在使用sns_nsn替換a1a_1a1得到新的集合Snew={a2,a3,...an,sn}S_{new}=\{a_2,a_3,...a_n,s_n\}Snew={a2,a3,...an,sn}，則∑2nai+sn≥sum1\sum_2^nai+s_n\geq sum_1∑2nai+sn≥sum1,即S’‘可以作為最優(yōu)解甚至刪除S’'中的a2a_2a2之后，仍然是滿足要求的,綜上，最優(yōu)解中一定包含S中最大的正整數(shù)。
   最優(yōu)子結(jié)構(gòu)：略。

2. 時間復(fù)雜度：排序的平均時間復(fù)雜度是O(nlgn)O(nlgn)O(nlgn)的，下面的循環(huán)是O(n)O(n)O(n)的，所以算法整體是O(nlgn)O(nlgn)O(nlgn)的。

題目七

現(xiàn)有一塊草坪，長為m米，寬為n米，要在橫中心線上放置半徑為Ri的噴水裝置，每個噴水裝置的效果都會讓以它為中心的半徑為實數(shù)Ri的圓被濕潤，設(shè)有充足的噴水裝置，并且一定能把草坪全部濕潤，設(shè)計算法選擇盡量少的噴水裝置，把整個草坪的全部濕潤。要求寫出偽代碼并分析算法正確性和復(fù)雜性。

噴水裝置的噴灌范圍是圓形，如上圖所示，最靠左的裝置一定可以噴灌到矩形的左上角，第一個裝置形成的圓形記為S1，第二是S2，則S1和S2的交點一定在矩形的邊界線上。
策略是選擇噴灌范圍最大的噴灌裝置，直到選擇的裝置可以噴灌整個矩形草坪。假設(shè)R1≥R2≥R3...≥RnR_1\geq R_2\geq R_3...\geq RnR1≥R2≥R3...≥Rn
最優(yōu)解是選擇R1≥R2≥R3...≥RmR_1\geq R_2\geq R_3...\geq R_mR1≥R2≥R3...≥Rm
使得∑i=1mRi2?n2/4≥m\sum_{i=1}^m\sqrt{R_i^2-n^2/4}\geq m∑i=1mRi2?n2/4≥m且∑i=1m?1Ri2?n2/4<m\sum_{i=1}^{m-1}\sqrt{R_i^2-n^2/4}< m∑i=1m?1Ri2?n2/4<m
算法正確性的證明，利用上面這個式子，就可以很簡單的說明貪心選擇性，最優(yōu)子結(jié)構(gòu)還是一樣的套路。
時間復(fù)雜度O(nlgn)O(nlgn)O(nlgn)

題目八

設(shè)計貪心算法求解如下的最大生成樹問題。
輸入：無向連通圖G=(V,E)，非負加權(quán)函數(shù)w:ER+;
輸出：各邊權(quán)值之和達到最大值的生成樹T=(V,E’)
1.簡述算法的貪心思想；
2.敘述并證明問題的貪心選擇性；
3.敘述問題的優(yōu)化子結(jié)構(gòu)
4.用偽代碼表述算法并分析其時間復(fù)雜度

題目九

在黑板上寫了n個正數(shù)組成的一個數(shù)列，進行如下操作：每一次擦去其中兩個數(shù)a和b, 然后在數(shù)列中加入一個數(shù)a*b+1，如此下去黑板上只剩下一個數(shù)。在所有按這種方法最后得到的樹中，最大的數(shù)記為max，最小的數(shù)記為min，則該數(shù)列的極差M定義為M=max-min。對于給定數(shù)列，設(shè)計貪心算法計算出其極差M，要求分析算法的正確性，寫出算法的偽代碼并分析其復(fù)雜性。

題目十

哈工大的機器人研究團隊現(xiàn)有不同類型的登山機器人，這些登山機器人可以攜帶有限的能量登山。在登山過程中，登山機器人需要消耗一定能量，連續(xù)攀登的路程越長，其攀登的速度就越慢。在對m種不同類型的機器人進行性能測試時，已測定出機器人i連續(xù)攀登1，2，…，n米所用的時間分別為ti1, ti2, …, tin?，F(xiàn)在要對這m個機器人進行綜合性能測試，舉行機器人接力連續(xù)攀登演習(xí)。攀登的總高度為s米。規(guī)定每個機器人攀登1次，每次至少攀登1米，最多攀登n米，而且每個機器人攀登的高度必須是整數(shù)，即只能在整米處接力。安排每個機器人攀登適當?shù)母叨?，使完成接力攀登的總時間最短，完成下列問題。
例子：若有3個機器人，每個機器人連續(xù)攀登1,2,3米所用的時間如表中所示。每個機器人最多可以攀登3米，攀登的總高度為5米，則使完成接力攀登的總時間最短的安排方案為1號機器人攀登2米，2號機器人攀登2米，3號機器人攀登1米。

（1）證明該問題具有貪心選擇性；
（2）證明該問題具有優(yōu)化子結(jié)構(gòu)；
（3）根據(jù)該貪心選擇性和優(yōu)化子結(jié)構(gòu)用偽代碼寫出算法；
（4）分析算法的時間復(fù)雜度。