考研復(fù)習(xí)資料大匯總-在線瀏覽
2024-11-19 22:24本頁(yè)面
【正文】 ， j)是背包容量為 j，可選擇物品為 i，i+1， … ， n時(shí) 01背包問題的最優(yōu)值?？紤]下列實(shí)例：n=3, 物品重量 (w1, w2, w3)=(2, 3, 4), 物品價(jià)值 (p1, p2, p3)=(1, 2, 5), 背包容量 C=6解：m(1, 6)=max{ m(2, 6), m(2, 62)+1 }m(2, 6)=max{ m(3, 6), m(3, 63)+2 }m(2, 4)=max{ m(3, 4), m(3, 43)+2 }m(3, 6)=5m(3, 3)=0=5=5=6解向量為 (x1, x2, x3)=(1, 0, 1)m(3, 4)=5m(3, 1)=0動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 ———— 最長(zhǎng)公共子序列最長(zhǎng)公共子序列?若給定序列 X={x1, x2, …, x m}，則另一序列 Z={z1, z2, …, z k}，是 X的 子序列 是指存在一個(gè) 嚴(yán)格遞增下標(biāo)序列{i1, i2, …, ik}使得對(duì)于 所有 j=1, 2, …, k 有： zj = xij。?給定 2個(gè)序列 X和 Y，當(dāng)另一序列 Z既是 X的子序列又是Y的子序列時(shí)，稱 Z是序列 X和 Y的 公共子序列 。 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 ———— 最長(zhǎng)公共子序列的結(jié)構(gòu)最長(zhǎng)公共子序列的結(jié)構(gòu)設(shè)序列 X={x1,x2,…,xm}和 Y={y1,y2,…,yn}的最長(zhǎng)公共子序列為Z={z1,z2,…,zk} ，則(1)若 xm=yn，則 zk=xm=yn，且 Zk1是 Xm1和 Yn1的最長(zhǎng)公共子序列。(3)若 xm≠yn且 zk≠yn，則 Z是 X和 Yn1的最長(zhǎng)公共子序列。因此，最長(zhǎng)公共子序列問題具有 最優(yōu)子結(jié)構(gòu)性質(zhì) 。用 c[i][j] 記錄序列和的最長(zhǎng)公共子序列的長(zhǎng)度。當(dāng) i=0 或 j=0時(shí)，空序列是 Xi 和 Yj 的最長(zhǎng)公共子序列。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：計(jì)算最優(yōu)值計(jì)算最優(yōu)值由于在所考慮的子問題空間中，總共有 θ(mn)個(gè)不同的子問題，因此，用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率。 for (i = 1。 i++) c[i][0] = 0。 i = n。 for (i = 1。 i++) for (j = 1。 j++) { if (x[i]= =y[j]) { c[i][j]=c[i1][j1]+1。} else if (c[i1][j]=c[i][j1]) { c[i][j]=c[i1][j]。} else { c[i][j]=c[i][j1]。 } }}構(gòu)造最長(zhǎng)公共子序列void LCS(int i， int j， char *x， int **b){ if (i = =0 || j= =0) return。 coutx[i]。 else LCS(i， j1， x， b)。該問題要求高效地安排一系列爭(zhēng)用某一公共資源的活動(dòng)。貪心法 —— 活動(dòng)安排問題 設(shè)有 n 個(gè)活動(dòng)的集合 E={1,2,…,n }，其中每個(gè)活動(dòng)都要求使用同一資源，如演講會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。如果選擇了活動(dòng) i，則它在半開時(shí)間區(qū)間[si, fi)內(nèi)占用資源。也就是說，當(dāng) si≥fj 或 sj≥fi 時(shí)，活動(dòng) i 與活動(dòng) j 相容。 a[1]=true。 int count=1。 i=n。 j=i。 } else a[i]=false。 }各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組 s和 f 中且 按結(jié)束時(shí)間的非減序排列 貪心法 —— 活動(dòng)安排問題 由于輸入的活動(dòng)以其完成時(shí)間的 非減序 排列，所以算法 greedySelector每次總是選擇 具有最早完成時(shí)間 的相容活動(dòng)加入集合 A中。也就是說，該算法的貪心選擇的 意義是意義是 使剩余的可安排時(shí)使剩余的可安排時(shí)間段極大化間段極大化 ，以便安排盡可能多的相容活動(dòng)，以便安排盡可能多的相容活動(dòng) 。當(dāng)輸入的活動(dòng)已按結(jié)束時(shí)間的非減序排列，算法只需 O(n)的時(shí)間安排 n個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用公共資源。 貪心法 —— 活動(dòng)安排問題 例： 設(shè)待安排的 11個(gè)活動(dòng)的開始時(shí)間和結(jié)束時(shí)間 按結(jié)束時(shí)間的非減序排列 如下：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貪心法 —— 活動(dòng)安排問題 活動(dòng)安排問題 算法 greedySelector 的計(jì)算過程 如左圖所示。陰影長(zhǎng)條表示的活動(dòng)是已選入集合A的活動(dòng)，而空白長(zhǎng)條表示的活動(dòng)是當(dāng)前正在檢查相容性的活動(dòng)
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1