高中信息競賽貪心算法(文件)
【正文】 待 B機器完工。顯然這是最優(yōu)解。 {首位指針初始化 } for I := 1 to N do if 對于第 I小的工序 J，若 A[J] B[J] then begin Order[S] := J。 end。 i的時間 ti’=ti+1di仍然是早任務(wù) , 總罰款不變； ? 規(guī)范形式 : 所有早任務(wù)在遲任務(wù)前 , 且按限期非遞減排序 . ? 關(guān)鍵 : 選哪些作為早任務(wù) ? ? 不是任選一些任務(wù)作為早任務(wù)都是可行的 . 對于一個早任務(wù)集合 S, 如何判斷它是否可行呢 ? 只需要對 S內(nèi)的元素按限期非遞減排序 , 然后一一放置； ? 貪心算法：先把罰款 E中元素按照權(quán)值從大到小排序為 e1,e2,…按照 e1,e2,… 的順序，嘗試添加到當(dāng)前集合 S里； – 如果添加之后 S仍是獨立集，則添加成功 – 如果 S不是獨立集，則由定義知以后無論怎樣繼續(xù)添加元素，得到的集合都不可能重新成為獨立集，因此不能進行此添加操作； Description:一個單位時間任務(wù)是個作業(yè) ,如要在計算機上運行一個程序 ,它恰覆蓋一個單位的運行時間。…… 。如果任務(wù) i沒在時間 di之前結(jié)束 , 則導(dǎo)致罰款 wi。 例如 : 任務(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個時間空位都是空的。 按上述貪心策略選擇了任務(wù) 1,2,3,4,7,放棄任務(wù) 5,6。 每一次合并 ,多多可以把兩堆果子合并到一起 ,消耗的體力等于兩堆果子的重量之和。假定每個果子重量都為 1,并且已知果子的種類數(shù)和每種果子的數(shù)目 ,你的任務(wù)是設(shè)計出合并的次序方案 ,使多多耗費的體力最少 ,并輸出這個最小的體力耗費值。所以多多總共耗費體力 =3+12=15。 Output： 輸出包括一行 ,這一行只包含一個整數(shù) ,也就是最小的體力耗費值。 int main() { cinn。c[m]++。i=20210。i=n1。x=n1){minn=a[x]+a[x+1]。(x=namp。} if(b[y]+b[y+1]minnamp。} sum+=minn。y++。其壓縮率通常在 20%～ 90%之間。定長變碼需要 300,000位，而按表中變長編碼方案，文件的總碼長為： ?（ 45 1+13 3+12 3+16 3+9 4+5 4） 1000=224,000。 ?給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的編碼，可以大大縮短總碼長。 } coutsumendl。 if(p==1) x=x+2。y=blen1){minn=b[y]+b[y+1]。y=blen)){minn=a[x]+b[y]。} if(a[x]+b[y]minnamp。 if(a[x]+a[x+1]minnamp。c[i]。} m=0。i=n。 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。 【 培訓(xùn)試題 】 合并果子 1059 Input： 輸入包括兩行 ,第一行是一個整數(shù) n(1＝ n=10000),表示果子的種類數(shù)。可以先將 2堆合并 ,新堆數(shù)目為 3,耗費體力為 3。多多在合并果子時總共消耗的體力等于每次合并所耗體力之和。 六、最優(yōu)合并問題 ? 有 n個正整數(shù) , 每次可以合并兩個相鄰的數(shù)，得到他們的和 , 代價為相加后的新數(shù) . ? 按如何的順序把所有的數(shù)合并成一個 , 使得代價總和盡量小 ? ? 貪心法 : 每次采取代價最少的合并方案 ? 不一定得到最優(yōu)解 ! 最優(yōu)解為 74 Description：在一個果園里 ,多多已經(jīng)將所有的果子打了下來 ,而且按果子的不同種類分成了不同的堆。在考慮任務(wù) j時 ,如果有一個恰處于或前于dj的時間空位仍空著 ,則將任務(wù) j 賦與最近的這樣的空位 ,并填入 。 Input:第一行為一個 n(n=100)，表示 n個任務(wù)，以后 n行，每行兩個數(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]值較大的工作 ,此時 ,我們可以將工作按 w[i]從大到小進行排序 ,然后按排好的順序依次對工作進行安排 ,安排的規(guī)則為 :要使處理工作 i的時間既在 d[i]之內(nèi) ,又盡量靠后 。 d1,……,dn,(1≤d,≤n), 任務(wù) i要求在 di前完成 。該調(diào)度中的第一個任務(wù)開始于時間 0,結(jié)束于時 1。 ? 確定所有任務(wù)的執(zhí)行順序 , 使得最懲罰最小 。 end else begin Order[T] := J。 算法流程如下： for I := 1 to N do {求 M數(shù)組 } if A[I] B[I] then M[I] := A[I] else M[I] := B[I]； 將 M從小到大排序； S := 1。然后從第 1個開始處理，若Mi=ai，則將它排在從頭開始的已經(jīng)作業(yè)后面，若 Mi=bi，則將它排在從尾開始的作業(yè)前面。 可以大膽猜想 ,要使總的空閑的最少 ,就要把在 A機器上加工時間最短的部件最先加工 ,這樣使得 B機器能以最快的速度開始加工 。 【 輸出
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1