【正文】 } return C[1][n]。 } } C[i][j]=min+sum。 if (C[i][k1]+C[k+1][j]min) { min=C[i][k1]+C[k+1][j]。 k=j。 sum=0。 min=∞ 。 i=nd。 dn。 } C[n+1][n]=0。 C[i][i]=p[i]。 i=n。 C(i, j)=min{C(i, k1)+C(k+1, j)+ } (1≤ i≤ j≤ n, i ≤ k ≤ j) （ 式 3） ??jissp80 2022/2/9 Page 80 按對(duì)角線逐條計(jì)算 每一個(gè) C(i, j)和 R(i, j)，得到最終表。 0 1 2 3 4 1 0 2 0 3 0 4 0 5 0 0 1 2 3 4 1 1 2 2 3 3 4 4 5 (a) 二維表 C (b) 二維表 R 79 2022/2/9 Page 79 在二維表 C和 R中只需計(jì)算主對(duì)角線以上的元素。 為了在求出由 {r1, r2, … , rn}構(gòu)成的二叉查找樹的平均比較次數(shù)的同時(shí)得到最優(yōu)二叉查找樹 ， 設(shè)一個(gè)二維表R[n+1][n+1]， 其下標(biāo)范圍與二維表 C相同 ， R[i][j]表示二叉查找樹 T(i, j)的根結(jié)點(diǎn)的序號(hào) 。 雖然最后的結(jié)果是 C(1, n)，但遵循動(dòng)態(tài)規(guī)劃法的求解方法 ,需要求出所有較小子問題 C(i, j)的值，考慮從 {ri, …, rj}中選擇一個(gè)記錄 rk作為二叉查找樹的根結(jié)點(diǎn)，可以得到如下關(guān)系： })1),1(()1)1,((1{m i n11???????????????jkssskissskjkinkTrpkiTrpp中的層數(shù)＋在中的層數(shù)＋在?),( jiC76 2022/2/9 Page 76 }),1()1,({m i n}),1()1,({m i n}),1()1,({m i n})1),1(()1)1,((1{m i n),(111 11 111????? ?? ??????????????? ????????????????????????????????????????????jissjkijissjkssskisssjkijksjksssskiskisssskjkijkssskissskjkipjkCkiCpnkTrpkiTrppnkTrppkiTrppnkTrpkiTrppjiC中的層數(shù)在中的層數(shù)在中的層數(shù)在中的層數(shù)在中的層數(shù)＋在中的層數(shù)＋在77 2022/2/9 Page 77 因此，得到如下動(dòng)態(tài)規(guī)劃函數(shù)： C(i, i1)=0 (1≤ i≤ n+1) （ 式 1） C(i,i)=pi (1≤ i≤ n) （ 式 2） C(i,j)=min{C(i,k1)+C(k+1,j)+ } (1≤ i≤ j≤ n, i≤ k≤ j) （ 式 3） 設(shè)一個(gè)二維表 C[n+1][n+1]， 其中 C[i][j]表示二叉查找樹 T(i, j)的平均比較次數(shù) 。 ???niii cp1最優(yōu)二叉查找樹 2. “ 最優(yōu) ” 是指 ？ —— 最少平均比較次數(shù) 74 2022/2/9 Page 74 5 6 7 8 (a) (b) (c) 二叉查找樹示例 6 7 8 5 5 6 7 8 例如，集合 {5, 6, 7, 8}的查找概率是 {, , , }， (a)的平均比較次數(shù)是 1＋ 2+ 3+ 4=， (b)的平均比較次數(shù)是 2＋ 1+ 2+ 3=， (c)的平均比較次數(shù)是 3＋ 2+ 1+ 2=。 } return L[m][n]。 } else if (S[i][j]= =2) j。 i。 j0) { if (S[i][j]= =1) { z[k]=x[i]。 for (i0 amp。 j=n。 S[i][j]=3。 S[i][j]=2。 S[i][j]=1。 j=n。 i=m。 i++) //初始化第 0列 L[i][0]=0。 for (i=0。 j=n。 69 2022/2/9 第 5章 動(dòng)態(tài)規(guī)劃法 Page 69 (a) 長(zhǎng)度矩陣 L (b) 狀態(tài)矩陣 S 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 0 1 2 2 2 1 2 2 2 2 2 0 1 1 2 2 2 2 2 2 2 2 0 3 2 1 1 2 1 2 1 1 3 0 1 2 2 2 2 2 2 2 2 3 0 3 1 2 2 2 2 2 2 2 4 0 1 2 3 3 3 3 3 3 3 4 0 3 3 1 1 3 1 3 1 1 5 0 1 2 3 3 3 3 4 4 4 5 0 3 3 3 2 2 2 1 2 2 6 0 1 2 3 4 4 4 4 5 5 6 0 3 3 1 1 3 1 2 1 1 例：序列 X=(a, b, c, b, d, b)， Y=(a, c, b, b, a, b, d, b, b)，建立兩個(gè) (m+1) (n+1)的二維表 L和表 S，分別存放搜索過程中得到的子序列的長(zhǎng)度和狀態(tài)。 用 L[i][j]表示子序列 Xi和 Yj的最長(zhǎng)公共子序列的長(zhǎng)度 ， 可得如下動(dòng)態(tài)規(guī)劃函數(shù)： L[0][0]=L[i][0]=L[0][j]=0(1≤i≤m,1≤j≤n) （ 式 1） （式 2） ?????????????????1,1,} 1 ] [ j ]L [ i1 ] ,L [ i ] [ jm a x {1,1,11]1 ] [ jL [ iL [ i ] [ j ]jiyxjiyxjiji67 2022/2/9 第 5章 動(dòng)態(tài)規(guī)劃法 Page 67 由此，把序列 X={x1, x2,…, xm}和 Y={y1, y2,…, yn}的最長(zhǎng)公共子序列的搜索分為 m個(gè)階段，第 1階段，按照式 2計(jì)算X1和 Yj的最長(zhǎng)公共子序列長(zhǎng)度 L[1][j]（ 1≤ j≤ n），第 2階段，按照式 2計(jì)算 X2和 Yj的最長(zhǎng)公共子序列長(zhǎng)度 L[2][j]（ 1≤ j≤ n），依此類推，最后在第 m階段，計(jì)算 Xm和 Yj的最長(zhǎng)公共子序列長(zhǎng)度 L[m][j]（ 1≤ j≤ n），則 L[m][n]就是序列 Xm和 Yn的最長(zhǎng)公共子序列的長(zhǎng)度。最長(zhǎng)公共子序列問題就是在序列 X和 Y的公共子序列中查找長(zhǎng)度最長(zhǎng)的公共子序列。設(shè)第 j 件物品的價(jià)格為 v[j]，重要度為 w[j]，共選中了 k 件物品，編號(hào)依次為 j1...jk，則所求的總和為：v[j1]*w[j1]+..+v[jk]*w[jk]請(qǐng)你幫助 小 明設(shè)計(jì)一個(gè)滿足要求的購物單 . 64 輸入實(shí)例 ? C=1000 n=5 ? 800 2 ? 400 5 ? 300 5 ? 400 3 ? 200 2 65 2022/2/9 第 5章 動(dòng)態(tài)規(guī)劃法 Page 65 對(duì)給定序列 X=(x1, x2,… , xm)和序列 Z=(z1, z2,… , zk)， Z是 X的子序列當(dāng)且僅當(dāng)存在一個(gè)嚴(yán)格遞增下標(biāo)序列 (i1, i2,… , ik)， 使得對(duì)于所有 j=1, 2, … , k， 有 zj=xij（ 1≤ij≤m） 。他還從網(wǎng)上查到了每件物品的價(jià)格（都是整數(shù)元）。今天一早小明就開始做預(yù)算，但是他想買的東西太多了，肯定會(huì)超過媽媽限定的 N 元。 } return V[n][C]。 j=jw[i]。 i0。 j=C。 j++) if (jw[i]) V[i][j]=V[i1][j]。 i++) //計(jì)算第 i行 ， 進(jìn)行第 i次迭代 for (j=1。 62 2022/2/9 第 6章 動(dòng)態(tài)規(guī)劃法 Page 62 算法 —— 0/1背包問題 for (i=1。 j=C。 i++) //初始化第 0列 V[i][0]=0。由此，得到如下函數(shù)： ??????????),1(),(,1),1(),(0jiVjiVwjjjiVjiVxii（式 3） 61 2022/2/9 第 6章 動(dòng)態(tài)規(guī)劃法 Page 61 算法實(shí)現(xiàn) 設(shè) n個(gè)物品的重量存儲(chǔ)在數(shù)組 w[n]中 ， 價(jià)值存儲(chǔ)在數(shù)組v[n]中 ， 背包容量為 C， 數(shù)組 V[n+1][C+1]存放迭代結(jié)果 ，其中 V[i][j]表示前 i個(gè)物品裝入容量為 j的背包中獲得的最大價(jià)值 ， 數(shù)組 x[n]存儲(chǔ)裝入背包的物品 ， 動(dòng)態(tài)規(guī)劃法求解 0/1背包問題的算法如下： 算法 —— 0/1背包問題 int KnapSack(int n, int w[ ], int v[ ]) { for (i=0。 為了確定裝入背包的具體物品，從 V(n,C)的值向前推，如果 V(n,C)V(n1,C)，表明第 n個(gè)物品被裝入背包，前 n1個(gè)物品被裝入容量為 Cwn的背包中；否則，第 n個(gè)物品沒有被裝入背包，前 n1個(gè)物品被裝入容量為 C的背包中。 0 1 2 3 4 5 6 7 8 9 10 0 w1=2 v1=6 1 w2=2 v2=3 2 w3=6 v3=5 3 w4=5 v4=4 4 w5=4 v5