貪心算法習(xí)題

1、【問(wèn)題描述問(wèn)題描述】 有n個(gè)人在一個(gè)水龍頭前排隊(duì)接水。假如每個(gè)人接水的時(shí)間為T(mén)i，請(qǐng)編程找出這n個(gè)人排隊(duì)的一種順序，使得n個(gè)人的平均等待時(shí)間最小?！締?wèn)題描述問(wèn)題描述】 我們計(jì)劃組織一個(gè)獨(dú)木舟旅行。租用的獨(dú)木舟都是一樣的，最多乘兩人，而且載重有一個(gè)限度?，F(xiàn)在要節(jié)約費(fèi)用，所以要盡可能地租用最少的舟。你的任務(wù)是讀入獨(dú)木舟的載重量，參加旅行的人數(shù)以及每個(gè)人的體重，計(jì)算出所需要的租船數(shù)目。【樣例輸入樣例輸入】 獨(dú)木舟載重量：100人數(shù)：9體重： 90 20 20 30 50 60 70 80 90基于貪心法，找到一個(gè)重量最大的人，讓它盡可能與重量大的人同乘一船。如此循環(huán)直至所有人都分配完畢即可統(tǒng)計(jì)出所需

2、要的獨(dú)木舟數(shù)。【問(wèn)題描述問(wèn)題描述】 小偉報(bào)名參加電視臺(tái)的智力大沖浪節(jié)目。本次挑戰(zhàn)賽吸引了眾多參賽者，主持人為了表彰大家的勇氣，先獎(jiǎng)勵(lì)每個(gè)參賽者m元。先不要太高興！因?yàn)檫@些錢(qián)還不一定都是你的！接下來(lái)，主持人宣布了比賽規(guī)則：首先，比賽時(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ù)是不一樣的。當(dāng)然，每個(gè)游戲本身都很簡(jiǎn)單，保證每個(gè)參賽者都能在一個(gè)時(shí)段內(nèi)完成，而且都必須從整時(shí)段開(kāi)始。主持人只是想考考每個(gè)參賽者如何安排組織自己做游戲的順序。作為參賽者，

3、小偉如何贏取最多的錢(qián)！【樣例樣例】輸入 初始獎(jiǎng)金：10000 游戲個(gè)數(shù)：7 結(jié)束時(shí)段：4 2 4 3 1 4 6 罰款金額：70 60 50 40 30 20 10 輸出 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ù)，則把其扔

4、到最大的一個(gè)空時(shí)間段內(nèi)。這樣做的效果必然是最優(yōu)的，因?yàn)椴荒芡瓿傻娜蝿?wù)，在任意一個(gè)時(shí)間段中罰款數(shù)目都是一樣的。一位管理項(xiàng)目的經(jīng)理想要確定每個(gè)月一位管理項(xiàng)目的經(jīng)理想要確定每個(gè)月需要的工人數(shù)量。他當(dāng)然知道每月所需需要的工人數(shù)量。他當(dāng)然知道每月所需的最少工人數(shù)。當(dāng)他雇傭或解雇一個(gè)工的最少工人數(shù)。當(dāng)他雇傭或解雇一個(gè)工人時(shí)，會(huì)有一些額外支出。一旦一個(gè)工人時(shí)，會(huì)有一些額外支出。一旦一個(gè)工人被雇傭，即使他不工作，他也將得到人被雇傭，即使他不工作，他也將得到工資。這位經(jīng)理知道雇傭一個(gè)工人的費(fèi)工資。這位經(jīng)理知道雇傭一個(gè)工人的費(fèi)用、解雇一個(gè)工人的費(fèi)用和一個(gè)工人的用、解雇一個(gè)工人的費(fèi)用和一個(gè)工人的工資。現(xiàn)在，他在考慮

5、一個(gè)問(wèn)題：為了工資?，F(xiàn)在，他在考慮一個(gè)問(wèn)題：為了把項(xiàng)目的費(fèi)用控制在最低水平上，他將把項(xiàng)目的費(fèi)用控制在最低水平上，他將每月雇傭或解雇多少個(gè)工人。每月雇傭或解雇多少個(gè)工人?！据斎胼斎搿?輸入文件含有三行。第一行為月數(shù)n（不超過(guò)12）。第二行含有雇傭一個(gè)工人的費(fèi)用、一個(gè)工人的工資和解雇一個(gè)工人的費(fèi)用（=100）。第三行含n個(gè)數(shù)，分別表示每月最少需要的工人數(shù)（=1000）。每個(gè)數(shù)據(jù)之間有一個(gè)空格隔開(kāi)?！据敵鲚敵觥?輸出僅一行，表示項(xiàng)目的最小總費(fèi)用?！緲永斎霕永斎搿?3 4 5 6 10 9 11【樣例輸出樣例輸出】 199我們從第一個(gè)月開(kāi)始，逐月計(jì)算現(xiàn)有工人數(shù)，先給這些工人發(fā)放工資。如果雇傭了新工

6、人，則必須給新上崗人員發(fā)放雇傭費(fèi)用；如果削減了部分工人，則必須給下崗人員發(fā)放解雇費(fèi)用。當(dāng)月發(fā)放的工資+雇傭（或解雇）費(fèi)用構(gòu)成了一個(gè)月的總費(fèi)用。我們從第一個(gè)月開(kāi)始，逐月累計(jì)項(xiàng)目總費(fèi)用，直至計(jì)算出n個(gè)月的總費(fèi)用時(shí)為止。問(wèn)題是，怎樣將這筆費(fèi)用控制在最低水平上？設(shè)mincost表示最小費(fèi)用和，初始時(shí)，mincost=0；now表示現(xiàn)有工人數(shù)，初始時(shí)，now=0；mini表示第i個(gè)月所需要的最少工人數(shù)（1=I now then begin mincost := mincost + h * (mini - now); now := mini; end;mincost := mincost + now *

7、s; 顯然，這樣的雇傭費(fèi)用支出是最節(jié)省的如果現(xiàn)有工人數(shù)now大于第i個(gè)月最少需要的工人數(shù)mini，則需要解雇一部分工人最佳方案是否一定是解雇（now-mini）個(gè)工人呢？不一定是的。例如，對(duì)于示例中的數(shù)據(jù)，依上述方法計(jì)算：第1個(gè)月雇傭10人：mincost = mincost + h * (mini - now) + s * mini = 0+4*10+5*10 = 90 now = 10 (注意：h=4, s=5, f=6; )第2個(gè)月解雇1人，使得現(xiàn)有工人數(shù)為9人：mincost = mincost + f * (now - min2)+s * min2 = 90+6*1+9*5 = 14

8、1 now = 9第3個(gè)月雇傭2人，使得現(xiàn)有工人數(shù)為11人：mincost = mincost + h * (min3 - now) + s * min3 =141+4*2+5*11 = 204 now = 11顯然，該雇傭計(jì)劃的總費(fèi)用（顯然，該雇傭計(jì)劃的總費(fèi)用（204204）并）并不是最少的，因?yàn)槿绻诓皇亲钌俚?，因?yàn)槿绻? 2個(gè)月不解雇個(gè)月不解雇1 1人，仍維持人，仍維持1010人，第人，第3 3個(gè)月再雇傭個(gè)月再雇傭1 1人，人，這種情況下的總費(fèi)用為（這種情況下的總費(fèi)用為（4 4* *10+510+5* *1010）+(5+(5* *10)+(410)+(4* *1+51+5* *11)

9、=90+50+59=19911)=90+50+59=199，即為樣例輸出。即為樣例輸出。由此看出，解雇的人數(shù)應(yīng)比（now-mini）少一些，那么少多少呢？我們采取這樣的貪心策略去確定： 盡可能少地解雇工人(Why?)，并且，在工資支出合理的前提下，盡可能使現(xiàn)有工人數(shù)維持在一個(gè)最長(zhǎng)時(shí)間內(nèi)，以減少雇傭和解雇的額外支出。實(shí)現(xiàn)的方法是：在實(shí)現(xiàn)的方法是：在miniminnminiminn間，間，按最少需要人數(shù)遞增的順序，將月份排按最少需要人數(shù)遞增的順序，將月份排成序列成序列y y1 1，y y2 2，y yn-in-i，y yn-i+1n-i+1（其中（其中i=yi=yj j=n=n，1=j=n-i+1

10、1=j=n-i+1）。）。從第yj個(gè)月出發(fā)，按照最少需要遞減的順序來(lái)檢查minyj、minyj-1、，一旦發(fā)現(xiàn)第yj月超員(問(wèn)題：為什么是倒序檢查？能否正序檢查？)，且這些工人在第yj+1個(gè)月雇傭與第i到第yj月期間解雇的總費(fèi)用，比第i到第yj個(gè)月連續(xù)使用的費(fèi)用節(jié)約，即： （minyjnow）and (f+hs*(yj+1-i) and (yj+1=n) or (fn) 則在第i個(gè)月解雇now-minyj個(gè)工人，使現(xiàn)有工人數(shù)變?yōu)閙inyj，否則，維持現(xiàn)有工人數(shù)不變。在miniminn間，按最少需要人數(shù)遞增的順序，將月份排成y1，yn-i+1;for j := n i downto 1 do 思考：為何要倒推？ if (minyjnow) and (f+h*ord(yj+1=n) now then if mini now then 在現(xiàn)有人數(shù)不足的情況下，確定第在現(xiàn)有人數(shù)不足的情況下，確定第i i個(gè)月的雇傭方案，個(gè)月的雇傭方案， 并累計(jì)最小費(fèi)用并累計(jì)最小費(fèi)用mincost;mincost; else else 在現(xiàn)有人數(shù)多余的情況下，確定第在現(xiàn)有人數(shù)多余的情況下，確