版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
貪心策略貪心方法的基本思想
貪心是一種解題策略,也是一種解題思想使用貪心方法需要注意局部最優(yōu)與全局最優(yōu)的關(guān)系,選擇當(dāng)前狀態(tài)的局部最優(yōu)并不一定能推導(dǎo)出問題的全局最優(yōu)利用貪心策略解題,需要解決兩個(gè)問題:該題是否適合于用貪心策略求解如何選擇貪心標(biāo)準(zhǔn),以得到問題的最優(yōu)/較優(yōu)解引入:排隊(duì)打水問題有N個(gè)人同時(shí)排隊(duì)到R個(gè)水龍頭去打水,他們裝滿水桶的時(shí)間為T1,T2,…,Tn為整數(shù)且各不相等,應(yīng)如何安排他們的打水順序才能使他們所有人打水的時(shí)間總和最少?說明:每個(gè)人打水的時(shí)間包含他等待的時(shí)間。分析由于排隊(duì)時(shí),越靠前面的計(jì)算的次數(shù)越多,顯然越小的排在越前面得出的結(jié)果越?。梢杂脭?shù)學(xué)方法簡(jiǎn)單證明,這里就不再贅述),所以這道題可以用貪心法解答,基本步驟:將輸入的時(shí)間按從小到大排序;將排序后的時(shí)間按順序依次放入每個(gè)水龍頭的隊(duì)列中;統(tǒng)計(jì),輸出答案。例1排序機(jī)器(Sort)有一個(gè)機(jī)器叫做排序機(jī),他可以對(duì)一個(gè)無序序列排序。它有兩種操作,一種是將某個(gè)數(shù),放到第一位;還有一種是將某個(gè)數(shù)放到最后一位。比如對(duì)于序列: {8,12,25,7,15,19} MOVEFRONT7{7,8,12,25,15,19} MOVEBACK25{7,8,12,15,19,25}
于是整個(gè)序列就排好序了?,F(xiàn)在請(qǐng)你寫個(gè)程序,計(jì)算某個(gè)序列需要最少多少次操作,才能變成從小到大排好序的序列。輸入格式
第一行一個(gè)數(shù)N,表示有N個(gè)元素有待排序。
第二行N個(gè)數(shù),用空格隔開,表示要排序的N個(gè)數(shù)。
輸出格式
一行一個(gè)數(shù)表示需要的操作次數(shù)。排序機(jī)器(Sort)輸入樣例 6 8122571519
輸出樣例 2數(shù)據(jù)規(guī)模
對(duì)于30%的數(shù)據(jù)N≤50;
對(duì)于60%的數(shù)據(jù)N≤1000;
對(duì)于100%的數(shù)據(jù)N≤100000,要排序的每個(gè)數(shù)都不相同。分析首先可以發(fā)現(xiàn)一個(gè)顯然的結(jié)論:只要合理移動(dòng),每個(gè)數(shù)最多移動(dòng)一次(因?yàn)槿绻粋€(gè)數(shù)移動(dòng)了超過一次,那么只有最后一次移動(dòng)是有效的)那么我們就要找到最大的不動(dòng)點(diǎn)集,假設(shè)為集合x,考慮到其余的點(diǎn)都移動(dòng)過,因此在最后set(x)的點(diǎn)是全部貼在一起的,因此需要滿足x中的所有點(diǎn)在最終結(jié)果(既將a排序后的序列)中是連續(xù)的。求出最大的集合只需掃一遍原數(shù)組即可。例2:停“房”(Parking)題目描述
在一棵N個(gè)節(jié)點(diǎn)的有根樹上,有一只蝸牛停在節(jié)點(diǎn)P上,其他還有K只蝸牛停在節(jié)點(diǎn)Si上。
現(xiàn)在這只停在P上的蝸牛,想要去根節(jié)點(diǎn),將自己的房子停在那里。由于兩只蝸牛如果同時(shí)出現(xiàn)在一個(gè)節(jié)點(diǎn)上會(huì)造成危險(xiǎn),所以你需要調(diào)度這些蝸牛,使得P到根的路徑上沒有別的蝸牛。可是蝸牛只能向葉子節(jié)點(diǎn)的方向爬,現(xiàn)在你希望知道所有蝸牛至少走幾步(走的步數(shù)總和最小),才能使得根到P的路徑上沒有別的蝸牛。輸入樣例
第一行三個(gè)數(shù)N,P和K。
接下來N行,每行格式如下:
T
A1
A2…AT
第i+1行表示,第i個(gè)點(diǎn)有T個(gè)兒子,分別是A1~AT。
最后一行K個(gè)數(shù),表示其他K蝸牛的停房地點(diǎn),保證Si≠P。
輸出格式
一個(gè)數(shù),表示其他蝸牛最少要移動(dòng)多少步。數(shù)據(jù)規(guī)模
對(duì)于40%的數(shù)據(jù)N≤20;
對(duì)于100%的數(shù)據(jù)2≤N≤5000,2≤P≤N,0≤K≤N-2。分析首先考慮到,蝸牛之間是沒有差別的,可以發(fā)現(xiàn)以下結(jié)論:在a->c的路徑上有b,那么a->b,b->c和a->c是沒有差別的,因此我們可以對(duì)每只蝸牛分開考慮。既在p->1的路徑上,如果存在某只擋路的蝸牛,那么只需在此蝸牛的子樹中找一個(gè)可行的離其最近的點(diǎn)即可,復(fù)雜度n^2例3:求最大得分對(duì)任意給定自然數(shù)集合W={m..n}(m,n≤100)若存在某個(gè)數(shù)p∈W;并且p至少是W中其他某個(gè)數(shù)的因數(shù);則刪除p和它的倍數(shù)后,得到p分;重復(fù)第2步,直到不能再刪除為止;求集合W的最大得分.例如W={3,4,5,6,7,8,9,10}刪除5,W={3,4,6,7,8,9}刪除4,W={3,6,7,9}刪除3,W={7}總得分為5+4+3=12基本思路初看這一問題,很容易想到用貪心策略來求解,即選擇集合中最大的可以刪除的數(shù)開始刪起,直到不能再刪除為止,而且通過一些簡(jiǎn)單的例子來驗(yàn)證,這一貪心標(biāo)準(zhǔn)似乎也是正確的,例如,當(dāng)m=2,n=10時(shí),集合W={2,3,…,10},運(yùn)用上述“貪心標(biāo)準(zhǔn)”可以得到這一問題的d=5+4+3=121.a=5P={2,3,4,6,7,8,9}d=52.a=4P={2,3,6,7,9} d=5+4=93.a=3p={2,7} d=5+4+3=12分析但是,W={2,3,4,5,6,7,8,9,10}刪除5,W={2,3,4,6,7,8,9}刪除4,W={2,3,6,7,9}刪除2,W={3,7,9}刪除3,W={7}總得分為5+4+3+2=14問題出現(xiàn)在哪里呢??6既是3的倍數(shù)也是2的倍數(shù)!!算法改進(jìn)將原算法基礎(chǔ)上進(jìn)行改進(jìn)。下面給出新的算法:建立集合P={m..n}從ndiv2到m每數(shù)構(gòu)造一個(gè)集合c[i],包含該數(shù)在P中的所有倍數(shù)(不包括i本身)從ndiv2起找到第一個(gè)元素個(gè)數(shù)最少但又不為空的集合c[i]在d分值中加上i把i及c[i]集合從P集中刪除,更新所有構(gòu)造集合的元素檢查所有構(gòu)造集合,若還有非空集合,則繼續(xù)3步驟,否則打印、結(jié)束思考題1:最大排列(Perm)問題描述
給一個(gè)長(zhǎng)度為N的序列,每個(gè)元素都不相同。每次可以交換相鄰兩個(gè)元素,現(xiàn)在你最多可以交換K次,問你可通過交換得到的字典序最大的序列是什么。
輸入格式
第一行兩個(gè)數(shù)N和K。
第一行N個(gè)數(shù)。
輸出格式
一行N個(gè)數(shù)字,表示字典序最大的序列。
最大排列(Perm)輸入樣例 71 10203040506070
輸出樣例 20103040506070
數(shù)據(jù)規(guī)模
對(duì)于30%的數(shù)據(jù)N≤50;
對(duì)于100%的數(shù)據(jù)N≤5000。思考題2:旅行家的預(yù)算一個(gè)旅行家想駕駛汽車以最少的費(fèi)用從一個(gè)城市到另一個(gè)城市(假設(shè)出發(fā)時(shí)油箱時(shí)空的)。給定兩個(gè)城市之間的距離D1、汽車油箱的容量C(以升為單位)、每升汽油能行駛的距離D2、出發(fā)點(diǎn)每升汽油價(jià)格P和沿途加油站數(shù)N(N可以為零),油站i離出發(fā)點(diǎn)的距離Di、每升汽油價(jià)格Pi(i=1,2,……,N)。計(jì)算結(jié)果四舍五入至小數(shù)點(diǎn)后兩位。如果無法到達(dá)目的地,則輸出“NoSolution”。思考題3:刪數(shù)問題鍵盤輸入一個(gè)高精度的正整數(shù)N,去掉其中任意S個(gè)數(shù)字后剩下的數(shù)字按左右次序組成一個(gè)新的正整數(shù)。對(duì)給定的N和S,尋找一種刪數(shù)規(guī)則使得剩下得數(shù)字組成的新數(shù)最小。思考題4:數(shù)列極差問題
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年注冊(cè)健康管理師基礎(chǔ)模擬卷及答案
- 年輕干部培養(yǎng)選拔調(diào)研報(bào)告
- 題型七太陽對(duì)地球的影響-2023屆高考地理高頻題型專項(xiàng)講解
- 2024年福州汽車駕駛員客運(yùn)資格證考試題庫及答案
- 2024年溫州客運(yùn)從業(yè)資格證考試試題
- 2024年蕪湖小型客運(yùn)從業(yè)資格證考試題答案
- 2024年新疆貨運(yùn)從業(yè)資格證考試題
- 2024年永州道路客運(yùn)從業(yè)資格證考試模擬試題
- 2024年張家界道路運(yùn)輸客運(yùn)從業(yè)資格證考試模擬試題
- 2024年哈爾濱客運(yùn)考試口訣圖片高清
- 專利申請(qǐng)答復(fù)審查意見實(shí)用模板大全
- 原料藥生產(chǎn)質(zhì)量管理手冊(cè)
- 網(wǎng)店?duì)I運(yùn)實(shí)務(wù)說課稿課件
- 國際商法(第四版)
- 大體積砼測(cè)溫方案終極版
- (學(xué)歷考證)高等教育自學(xué)考試新舊專業(yè)對(duì)照表-(本科層次)
- 殺軟體動(dòng)物劑綜述課件
- 國際商法(第五版)第八章國際海上貨物運(yùn)輸與保險(xiǎn)法
- 小學(xué)語文人教四年級(jí)下冊(cè)(統(tǒng)編)(教研版)第四單元-《神話中的偷竊者》教學(xué)設(shè)計(jì)
- 游戲立項(xiàng)說明書
- 游樂設(shè)施安全管理手冊(cè)
評(píng)論
0/150
提交評(píng)論