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

貪心算法習(xí)題排隊(duì)接水【問(wèn)題描述】

有n個(gè)人在一個(gè)水龍頭前排隊(duì)接水。假如每個(gè)人接水的時(shí)間為T(mén)i，請(qǐng)編程找出這n個(gè)人排隊(duì)的一種順序，使得n個(gè)人的平均等待時(shí)間最小。獨(dú)木舟【問(wèn)題描述】

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

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

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

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

初始獎(jiǎng)金：10000

游戲個(gè)數(shù)：7

結(jié)束時(shí)段：4243146

罰款金額：70605040302010

輸出

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

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

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

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

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

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