貪心算法習題

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

2、要的獨木舟數(shù)?！締栴}描述問題描述】 小偉報名參加電視臺的智力大沖浪節(jié)目。本次挑戰(zhàn)賽吸引了眾多參賽者，主持人為了表彰大家的勇氣，先獎勵每個參賽者m元。先不要太高興！因為這些錢還不一定都是你的！接下來，主持人宣布了比賽規(guī)則：首先，比賽時間分為n個時段，它又給出了很多小游戲，每個小游戲都必須在規(guī)定期限 ti 前完成（1=ti=n）。如果一個游戲沒能在規(guī)定期限前完成，則要從獎勵費m元中扣去一部分錢wi，wi為自然數(shù)。不同的游戲扣去的錢數(shù)是不一樣的。當然，每個游戲本身都很簡單，保證每個參賽者都能在一個時段內(nèi)完成，而且都必須從整時段開始。主持人只是想考考每個參賽者如何安排組織自己做游戲的順序。作為參賽者，

3、小偉如何贏取最多的錢！【樣例樣例】輸入 初始獎金：10000 游戲個數(shù)：7 結束時段：4 2 4 3 1 4 6 罰款金額：70 60 50 40 30 20 10 輸出 9950因為不同的小游戲不能準時完成時，具有不同的扣款權數(shù)，而且是最優(yōu)解問題，所以，很容易就想到用貪心法來求解本題。根據(jù)貪心思想，應讓扣款數(shù)值大的盡量準時完成。這樣，我們就先把這些任務按照扣款的數(shù)目進行排序，把大的排在前面，先進行放置。假如罰款最多的一個任務的完成期限是k，我們應該把它安排在哪個時段完成呢？應該放在第k個時段，因為放在1k中的任何一個位置上時，效果都是一樣的。一旦出現(xiàn)一個不可能在規(guī)定時限前完成的任務，則把其扔

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

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

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

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

8、1 now = 9第3個月雇傭2人，使得現(xiàn)有工人數(shù)為11人：mincost = mincost + h * (min3 - now) + s * min3 =141+4*2+5*11 = 204 now = 11顯然，該雇傭計劃的總費用（顯然，該雇傭計劃的總費用（204204）并）并不是最少的，因為如果第不是最少的，因為如果第2 2個月不解雇個月不解雇1 1人，仍維持人，仍維持1010人，第人，第3 3個月再雇傭個月再雇傭1 1人，人，這種情況下的總費用為（這種情況下的總費用為（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ù)應比（now-mini）少一些，那么少多少呢？我們采取這樣的貪心策略去確定： 盡可能少地解雇工人(Why?)，并且，在工資支出合理的前提下，盡可能使現(xiàn)有工人數(shù)維持在一個最長時間內(nèi)，以減少雇傭和解雇的額外支出。實現(xiàn)的方法是：在實現(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個月出發(fā)，按照最少需要遞減的順序來檢查minyj、minyj-1、，一旦發(fā)現(xiàn)第yj月超員(問題：為什么是倒序檢查？能否正序檢查？)，且這些工人在第yj+1個月雇傭與第i到第yj月期間解雇的總費用，比第i到第yj個月連續(xù)使用的費用節(jié)約，即： （minyjnow）and (f+hs*(yj+1-i) and (yj+1=n) or (fn) 則在第i個月解雇now-minyj個工人，使現(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個月的雇傭方案，個月的雇傭方案， 并累計最小費用并累計最小費用mincost;mincost; else else 在現(xiàn)有人數(shù)多余的情況下，確定第在現(xiàn)有人數(shù)多余的情況下，確