考研復(fù)習(xí)資料大匯總-文庫吧資料
2024-11-19 22:24本頁面
【正文】 ) { int n=。 采用重量最輕者先裝的貪心選擇策略 ，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。 貪心法 —— 最優(yōu)裝載 有一批集裝箱要裝上一艘載重量為 c 的輪船。各作業(yè)所需的處理時間分別為 {2, 14, 4, 16, 6, 5, 3}。然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理機。按此策略，當(dāng) 時，只要將機器 i 的 [0, ti]時間區(qū)間分配給作業(yè) i 即可。作業(yè)不能拆分成更小的子作業(yè)。對于這一類問題 ,用 貪心選擇策略 有時可以設(shè)計出較好的近似算法。作業(yè) i 所需的處理時間為 ti。i 1 2 3 4 5 6 7 8 9 10 11S[i]1 3 0 5 3 5 6 8 8 2 12f[i] 4 5 6 7 8 9 10 11 12 13 14貪心法 —— 多機調(diào)度問題多機調(diào)度問題 要求給出一種作業(yè)調(diào)度方案，使所給的 n個作業(yè)在盡可能短的時間內(nèi)由 m 臺機器加工處理完成。圖中每行相應(yīng)于算法的一次迭代。如果所給出的活動未按非減序排列，可以用 O(nlogn)的時間重排。算法 greedySelector的效率極高。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。 } return count。 count++。 i++) { if (s[i]=f[j]) { a[i]=true。 for (int i=2。 int j=1。在下面所給出的解活動安排問題的貪心算法 :int greedySelector(int s[], int f[], boolean a[]) { int n=。 若區(qū)間 [si, fi)與區(qū)間 [sj, fj)不相交，則稱 活動 i 與活動 j 是相容 的。每個活動 i 都有一個要求使用該資源的 起始時間 si 和一個 結(jié)束時間 fi ,且 si fi 。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。}貪心法 —— 活動安排問題 活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。 } else if (b[i][j]== 2) LCS(i1， j， x， b)。 if (b[i][j]== 1){ LCS(i1， j1， x， b)。 b[i][j]=3。 b[i][j]=2。 b[i][j]=1。 j = n。 i = m。 i++) c[0][i] = 0。 for (i = 1。 i = m。 void LCSLength(int m， int n， char *x， char *y， int **c， int **b){ int i， j。故此時c[i][j]=0。其中， Xi={x1,x2,…,xi}； Yj={y1,y2,…,yj}。 子問題的遞歸結(jié)構(gòu)子問題的遞歸結(jié)構(gòu)由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。由此可見， 2個序列的最長公共子序列包含了這 2個序列的前綴的最長公共子序列。(2)若 xm≠yn且 zk≠xm，則 Z是 Xm1和 Y的最長公共子序列。n給定 2個序列 X={x1, x2, …, xm}和 Y={y1, y2, …, yn}，找出 X和 Y的最長公共子序列。u 例如，序列 Z={B, C, D, B}是序列 X={A, B, C, B, D, A, B}的子序列，相應(yīng)的遞增下標(biāo)序列為 {2, 3, 5, 7}。由 01背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計算 m(i， j)的遞歸式如下。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大 ?01背包問題是一個特殊的整數(shù)規(guī)劃問題。動態(tài)規(guī)劃動態(tài)規(guī)劃 ——01 背包問題背包問題給定 n 種物品和一背包。這是使 T(n)=O(n)的關(guān)鍵之處。}復(fù)雜度分析T(n)=O(n)上述算法將每一組的大小定為 5，并選取 75作為是否作遞歸調(diào)用的分界點。 if (k=j) return Select(a,p,i,k)。 //找中位數(shù)的中位數(shù)， rp4即上面所說的 n5 Type x = Select(a, p, p+(rp4)/5, (rp4)/10)。 i=(rp4)/5。 }。Type Select(Type a[], int p, int r, int k){ if (rp75) { 用某個簡單排序算法對數(shù)組 a[p:r]排序 。同理，基準(zhǔn) x也至少比 3(n5)/10個元素小。分治法分治法 ———— 線性時間選擇線性時間選擇設(shè)所有元素互不相同。如果?n/5?是偶數(shù)，就找它的 2個中位數(shù)中較大的一個。用任意一種排序
公司管理相關(guān)推薦
鄂ICP備17016276號-1