高中信息競賽貪心算法-資料下載頁
2025-05-10 10:40本頁面
【正文】 。如果任務(wù) i沒在時(shí)間 di之前結(jié)束 , 則導(dǎo)致罰款 wi。 要求找出 S的一個(gè)調(diào)度 ,使之最小化總的罰款。 Input:第一行為一個(gè) n(n=100)，表示 n個(gè)任務(wù)，以后 n行，每行兩個(gè)數(shù) di和 wi分別表示期限和罰款 Output:最小化總的罰款 罰款問題 Sample Input 6 6 10 4 70 3 40 2 60 4 50 1 30 4 20 Sample Output: 50 【 算法分析 】 ： 要使罰款最少 ,我們顯然應(yīng)盡量完成 w[i]值較大的工作 ,此時(shí) ,我們可以將工作按 w[i]從大到小進(jìn)行排序 ,然后按排好的順序依次對工作進(jìn)行安排 ,安排的規(guī)則為 :要使處理工作 i的時(shí)間既在 d[i]之內(nèi) ,又盡量靠后 。如果 d[i]之內(nèi)的時(shí)間都已經(jīng)排滿 ,就放棄此項(xiàng)工作。 例如 : 任務(wù) i 1 2 3 4 5 6 7 期限 di 4 2 4 3 1 4 6 罰款 wi 70 60 50 40 30 20 10 最初 ,我們設(shè)所有 n個(gè)時(shí)間空位都是空的。然后按罰款的單調(diào)遞減順序 (任務(wù) 1,任務(wù) 2,任務(wù) 3,任務(wù) 4,任務(wù) 5,任務(wù) 6,任務(wù) 7)對各個(gè)子任務(wù)作貪心選擇。在考慮任務(wù) j時(shí) ,如果有一個(gè)恰處于或前于dj的時(shí)間空位仍空著 ,則將任務(wù) j 賦與最近的這樣的空位 ,并填入 。 如果不存在這樣的空位 ,則將任務(wù) j賦與一個(gè)還未被占的、最近的空位。 按上述貪心策略選擇了任務(wù) 1,2,3,4,7,放棄任務(wù) 5,6。最終的最優(yōu)調(diào)度為 〈 2,4,3,1,7,5,6〉 ,其總的罰款為 W5+W6＝ 50。 六、最優(yōu)合并問題 ? 有 n個(gè)正整數(shù) , 每次可以合并兩個(gè)相鄰的數(shù)，得到他們的和 , 代價(jià)為相加后的新數(shù) . ? 按如何的順序把所有的數(shù)合并成一個(gè) , 使得代價(jià)總和盡量小 ? ? 貪心法 : 每次采取代價(jià)最少的合并方案 ? 不一定得到最優(yōu)解 ! 最優(yōu)解為 74 Description：在一個(gè)果園里 ,多多已經(jīng)將所有的果子打了下來 ,而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。 每一次合并 ,多多可以把兩堆果子合并到一起 ,消耗的體力等于兩堆果子的重量之和。可以看出 ,所有的果子經(jīng)過 n1次合并之后 ,就只剩下一堆了。多多在合并果子時(shí)總共消耗的體力等于每次合并所耗體力之和。 因?yàn)檫€要花大力氣把這些果子搬回家 ,所以多多在合并果子時(shí)要盡可能地節(jié)省體力。假定每個(gè)果子重量都為 1,并且已知果子的種類數(shù)和每種果子的數(shù)目 ,你的任務(wù)是設(shè)計(jì)出合并的次序方案 ,使多多耗費(fèi)的體力最少 ,并輸出這個(gè)最小的體力耗費(fèi)值。 例如有 3種果子 ,數(shù)目依次為 1,2,9?？梢韵葘? 2堆合并 ,新堆數(shù)目為 3,耗費(fèi)體力為 3。接著 ,將新堆與原先的第三堆合并 ,又得到新的堆 ,數(shù)目為 12,耗費(fèi)體力為 12。所以多多總共耗費(fèi)體力 =3+12=15?？梢宰C明 15為最小的體力耗費(fèi)值。 【 培訓(xùn)試題 】 合并果子 1059 Input： 輸入包括兩行 ,第一行是一個(gè)整數(shù) n(1＝ n=10000),表示果子的種類數(shù)。第二行包含 n個(gè)整數(shù) ,用空格分隔 ,第 i個(gè)整數(shù) ai(1＝ ai=20210)是第 i種果子的數(shù)目。 Output： 輸出包括一行 ,這一行只包含一個(gè)整數(shù) ,也就是最小的體力耗費(fèi)值。輸入數(shù)據(jù)保證這個(gè)值小于 231。 Sample Input： 3 1 2 9 Sample Output： 15 【 數(shù)據(jù)規(guī)模 】 對于 30％的數(shù)據(jù) ,保證有 n=1000： 對于 50％的數(shù)據(jù) ,保證有 n=5000； 對于全部的數(shù)據(jù) ,保證有 n=10000。 long long a[10001],b[10001],c[20211]={0},m,n,i,p,x=1,y=1,minn,sum=0,blen=0。 int main() { cinn。 for(i=1。i=n。i++) {cinm。c[m]++。b[i]=2021000000。} m=0。 for(i=1。i=20210。i++) while(c[i]) {a[++m]=i。c[i]。} for(i=1。i=n1。i++) { minn=2021000000。 if(a[x]+a[x+1]minnamp。amp。x=n1){minn=a[x]+a[x+1]。p=1。} if(a[x]+b[y]minnamp。amp。(x=namp。amp。y=blen)){minn=a[x]+b[y]。p=2。} if(b[y]+b[y+1]minnamp。amp。y=blen1){minn=b[y]+b[y+1]。p=3。} sum+=minn。b[++blen]=minn。 if(p==1) x=x+2。 if(p==2){x++。y++。} if(p==3) y=y+2。 } coutsumendl。 核心代碼 七、 Huffman編碼 ? 給 n個(gè)字符的頻率，設(shè)計(jì) Huffman編碼 , 即給出每個(gè)字符的編碼串 (01串 ), 使得任意兩個(gè)編碼串互不為前綴 , 且總編碼長度 (每個(gè)字符的頻率與串長乘積之和 )最小 ?哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在 20%～ 90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個(gè)用 0， 1串表示各字符的最優(yōu)表示方式。 ?給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的編碼，可以大大縮短總碼長。 例如一個(gè)包含 100,000個(gè)字符的文件，各字符出現(xiàn)頻率不同，如下表所示。定長變碼需要 300,000位，而按表中變長編碼方案，文件的總碼長為： ?（ 45 1+13 3+12 3+16 3+9 4+5 4） 1000=224,000。 八、最小生成樹 九、單源最短路徑
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號-1