算法分析貪心算法習(xí)題-課件

貪心算法習(xí)題排隊接水【問題描述】

有n個人在一個水龍頭前排隊接水。假如每個人接水的時間為Ti，請編程找出這n個人排隊的一種順序，使得n個人的平均等待時間最小。獨木舟【問題描述】

我們計劃組織一個獨木舟旅行。租用的獨木舟都是一樣的，最多乘兩人，而且載重有一個限度。現(xiàn)在要節(jié)約費用，所以要盡可能地租用最少的舟。你的任務(wù)是讀入獨木舟的載重量，參加旅行的人數(shù)以及每個人的體重，計算出所需要的租船數(shù)目?！緲永斎搿?/p>

獨木舟載重量：100人數(shù)：9體重：902020305060708090算法分析基于貪心法，找到一個重量最大的人，讓它盡可能與重量大的人同乘一船。如此循環(huán)直至所有人都分配完畢即可統(tǒng)計出所需要的獨木舟數(shù)。噴水裝置現(xiàn)有一塊草坪，長為20米，寬為2米，要在橫中心線上放置半徑為Ri的噴水裝置，每個噴水裝置的效果都會讓以它為中心的半徑為實數(shù)Ri(0<Ri<15)的圓被濕潤，這有充足的噴水裝置i（1<i<600)個，并且一定能把草坪全部濕潤，你要做的是：選擇盡量少的噴水裝置，把整個草坪的全部濕潤。解題思路這個題目思路很容易想，肯定是優(yōu)先使用半徑大的噴水裝置。因為半徑越大的噴水裝置所能覆蓋的范圍就越大。其實這個確定優(yōu)先選擇哪一個的過程就是貪心選擇的過程。所以本題就是先對所有的噴水裝置半徑排序，計算出，每個噴水裝置所能覆蓋的長度。每次都選出當(dāng)前半徑最大的，直到能覆蓋完所有的草地。智力大沖浪【問題描述】

小偉報名參加電視臺的智力大沖浪節(jié)目。本次挑戰(zhàn)賽吸引了眾多參賽者，主持人為了表彰大家的勇氣，先獎勵每個參賽者m元。先不要太高興！因為這些錢還不一定都是你的！接下來，主持人宣布了比賽規(guī)則：問題描述首先，比賽時間分為n個時段，它又給出了很多小游戲，每個小游戲都必須在規(guī)定期限ti

前完成（1<=ti<=n）。如果一個游戲沒能在規(guī)定期限前完成，則要從獎勵費m元中扣去一部分錢wi，wi為自然數(shù)。不同的游戲扣去的錢數(shù)是不一樣的。問題描述當(dāng)然，每個游戲本身都很簡單，保證每個參賽者都能在一個時段內(nèi)完成，而且都必須從整時段開始。主持人只是想考考每個參賽者如何安排組織自己做游戲的順序。作為參賽者，小偉如何贏取最多的錢！【樣例】輸入

初始獎金：10000

游戲個數(shù)：7

結(jié)束時段：4243146

罰款金額：70605040302010

輸出

9950分析因為不同的小游戲不能準(zhǔn)時完成時，具有不同的扣款權(quán)數(shù)，而且是最優(yōu)解問題，所以，很容易就想到用貪心法來求解本題。根據(jù)貪心思想，應(yīng)讓扣款數(shù)值大的盡量準(zhǔn)時完成。這樣，我們就先把這些任務(wù)按照扣款的數(shù)目進行排序，把大的排在前面，先進行放置。假如罰款最多的一個任務(wù)的完成期限是k，我們應(yīng)該把它安排在哪個時段完成呢？應(yīng)該放在第k個時段，因為放在1~k中的任何一個位置上時，效果都是一樣的。分析一旦出現(xiàn)一個不可能在規(guī)定時限前完成的任務(wù)，則把其扔到最大的一個空時間段內(nèi)。這樣做的效果必然是最優(yōu)的，因為不能完成的任務(wù)，在任意一個時間段中罰款數(shù)目都是一樣的。刪數(shù)問題

通過鍵盤輸入一個高精度的n(n≤240)位正整數(shù)N，去掉其中任意s個數(shù)字后，剩下的數(shù)字按原左右次序?qū)⒔M成一個新的正整數(shù)。編程對給定的n和s，尋找一種方案，使得剩下的數(shù)字組成的新數(shù)最小。輸入：Ns

輸出：最后剩下的最小數(shù)樣例輸入：178543S=4樣例輸出：13問題分析由于正整數(shù)N的有效位數(shù)最大可達240位，所以可以采用字符串類型來存儲N應(yīng)如何來確定該刪除哪s位呢？是不是只要刪掉最大的s個數(shù)字就可以了呢？問題分析為了盡可能地逼近目標(biāo)，我們選取的貪心策略為：每一步總是選擇一個使剩下的數(shù)最小的數(shù)字刪去，即按高位到低位的順序搜索，若各位數(shù)字遞增，則刪除最后一個數(shù)字，否則刪除第一個遞減區(qū)間的首字符。然后回到串首，按上述規(guī)則再刪除下一個數(shù)字。重復(fù)以上過程s次，剩下的數(shù)字串便是問題的解了。問題分析例如：n=178543s=4

刪數(shù)的過程如下：

n=178543{刪掉8}n=17543{刪掉7}n=1543{刪掉5}n=143{刪掉4}n=13{解為13}

輸入s,n;whiles>0do{i:=1;{從串首開始找}while(i