【正文】 當背包容量 c很大時，算法需要的計算時間較多。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大 ? 01背包問題是一個特殊的整數(shù)規(guī)劃問題。因此，在最壞情況下算法所需的計算時間為 O(nlogn)。進一步還可以證明，調(diào)度滿足 Johnson法則當且僅當對任意 ij有 由此可知， 所有滿足 Johnson法則的調(diào)度均為最優(yōu)調(diào)度。若?(1)=i, ?(2)=j。從而 T’=T(S,b?(1))。若 T’T(S,b?(1))，設(shè) ?’ 是作業(yè)集 S在機器 M2的等待時間為 b?(1)情況下的一個最優(yōu)調(diào)度。 流水作業(yè)調(diào)度 設(shè) ?是所給 n個流水作業(yè)的一個最優(yōu)調(diào)度，它所需的加工時間為 a?(1)+T’。 S?N是 N的作業(yè)子集。 流水作業(yè)調(diào)度問題要求確定這 n個作業(yè)的最優(yōu)加工順序，使得從第一個作業(yè)在機器 M1上開始加工，到最后一個作業(yè)在機器 M2上加工完成所需的時間最少。 另一方面 ，故又有 Size(i,j)≥Size(i1,j)， 從而 Size(i,j)=Size(i1,j)。在這種情況下 MNS(i,j){(i,π(i))}是 N(i1,π(i)1)的最大不相交子集。此時， 。 記 。導線 (i,π(i))稱為該電路板上的第 i條連線。因此整個算法所需的計算時間為 O(n)。顯而易見， l[1]， b[1]是 {p1,…,p l[1]}的最優(yōu)分段，且 l[i]， b[i]，是 {pl[1]+1,…,p n}的最優(yōu)分段。按此格式存儲象素序列{p1,p2,…,pn} ，需要 位的存儲空間。第 i個象素段 Si中 (1≤i≤m)，有 l[i]個象素 ,且該段中每個象素都只用b[i]位表示。時，顯然有 a+c≤m≤b+d (2)當 op[i+s]=39。 ?設(shè) m1是對子鏈 p(i， s)的任意一種合并方式得到的值，而 a和 b分別是在所有可能的合并中得到的最小值和最大值。游戲的得分就是所剩頂點上的整數(shù)值。 游戲第 1步，將一條邊刪除。由于在計算時還不知道 k的確切位置，而 k的所有可能位置只有 ji個，因此可以在這 ji個位置中選出使 t[i][j]值達到最小的位置。據(jù)此定義，要計算的凸 (n+1)邊形 P的最優(yōu)權(quán)值為 t[1][n]?？梢詳嘌?，由 T所確定的這 2個子多邊形的三角剖分也是最優(yōu)的。 ?矩陣連乘積中的每個矩陣 Ai對應(yīng)于凸 (n+1)邊形中的一條邊vi1vi。 三角剖分的結(jié)構(gòu)及其相關(guān)問題 ?一個表達式的完全加括號方式相應(yīng)于一棵完全二叉樹，稱為表達式的語法樹。弦將多邊形分割成 2個多邊形 {vi,vi+1,…,v j}和 {vj,vj+1,…v i}。因此，用 2行的數(shù)組空間就可以計算出最長公共子序列的長度。事實上，數(shù)組元素 c[i][j]的值僅由 c[i1][j1]， c[i1][j]和c[i][j1]這 3個數(shù)組元素的值所確定。 (x[i])。 12: else 13: c[i][j]=c[i][j1]。 j++) 6: if (x[i]==y[j]) 7: c[i][j]=c[i1][j1]+1。 4: for (int i = 1。 Algorithm lcsLength(x,y,b) 1: m?。故此時 C[i][j]=0。 子問題的遞歸結(jié)構(gòu) 由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。 (2)若 xm≠yn且 zk≠xm，則 Z是 xm1和 Y的最長公共子序列。例如，序列 Z={B， C，D， B}是序列 X={A， B， C， B， D， A， B}的子序列，相應(yīng)的遞增下標序列為 {2， 3， 5， 7}。 s[i][j] = k。 for (int k = i+1。 m?0 private static int lookupChain(int i, int j) { if (m[i][j] 0) return m[i][j]。 ?動態(tài)規(guī)劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結(jié)果。 ?利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個問題的最優(yōu)解。 ? 根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。 動態(tài)規(guī)劃思想 n T(n) = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) ? 如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復計算，從而得到多項式時間算法。這時只要讓這 2個選手進行比賽就可以了。這時只要讓這 2個選手進行比賽就可以了。 return d。 構(gòu)造 S1和 S2； //S1={p∈ S|x(p)=m}, S2={p∈ S|x(p)m} 2. d1=cpair2(S1)。對 P1中每一點最多只要檢查 P2中排好序的相繼 6個點。 22222 3625)3/2()2/())()(())()(( dddvyuyvxux ???????為了 確切地知道要檢查哪 6個點 ，可以將 p和P2中所有 S2的點投影到垂直線 l上。 ?因此，在分治法的合并步驟中 最多只需要檢查 6 n/2=3n個候選者 能否在線性時間內(nèi)找到 p3,q3？ 證明 :將矩形 R的長為 2d的邊 3等分，將它的長為d的邊 2等分，由此導出 6個 (d/2) (2d/3)的矩形。 ?遞歸地在 S1和 S2上找出其最小距離 d1和 d2，并設(shè)d=min{d1,d2}， S中的最接近點對或者是 d，或者是某個 {p,q}，其中 p∈ P1且 q∈ P2。 能否在線性時間內(nèi)找到 p3,q3？ 最接近點對問題 ?下面來考慮二維的情形。 ?由于在 S1中，每個長度為 d的半閉區(qū)間至多包含一個點（否則必有兩點距離小于 d），并且 m是 S1和 S2的分割點，因此(md,m]中至多包含 S中的一個點。最接近點對即為這 n個實數(shù)中相差最小的 2個實數(shù)。在快速排序算法的每一步中，當數(shù)組還沒有被劃分時，可以在 a[p:r]中隨機選出一個元素作為劃分基準，這樣可以使劃分基準的選擇是隨機的，從而可以期望劃分是較對稱的。 (a, i, p)。 ji{5, 6, 5, 2, 7, 8} j。 a[j] = x。 while (a[j].pareTo(x) 0)。目前最好的計算時間上界是 O() ?是否能找到 O(n2)的算法？？？目前為止還沒有結(jié)果。 ???????????????????222112112221121122211211BBBBAAAACCCC)( 2212111 BBAM ??2212112 )( BAAM ??1122213 )( BAAM ??)( 1121224 BBAM ??))(( 221122115 BBAAM ???))(( 222122126 BBAAM ???))(( 121121117 BBAAM ???624511 MMMMC ????2112 MMC ??4321 MMC ??731522 MMMMC ????復雜度分析 T(n)=O(nlog7) =O()?較大的改進 ? 22)()2/(7)1()(2 ??????? nnnOnTOnTStrassen矩陣乘法 ?傳統(tǒng)方法 ： O(n3) ?分治法 : O() ?更快的方法 ?? ?Hopcroft和 Kerr已經(jīng)證明 (1971)，計算 2個２ ２矩陣的乘積， 7次乘法是必要的。 ?是否能找到線性時間的算法？？？目前為止還沒有結(jié)果。 1. XY = ac 2n + ((ac)(bd)+ac+bd) 2n/2 + bd 2. XY = ac 2n + ((a+c)(b+d)acbd) 2n/2 + bd 復雜度分析 T(n)=O(nlog3) =O()?較大的改進 ? 11)()2/(3)1()(??????? nnnOnTOnT細節(jié)問題 ：兩個 XY的復雜度都是 O(nlog3)，但考慮到 a+c,b+d可能得到 m+1位的結(jié)果，使問題的規(guī)模變大，故不選擇第 2種方案。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn) 次。 if (x a[middle]) left = middle + 1。 據(jù)此容易設(shè)計出 二分搜索算法 ： public static int binarySearch(int [] a, int x, int n) { // 在 a[0] = a[1] = ... = a[n1] 中搜索 x // 找到 x時返回其在數(shù)組中的位置，否則返回 1 int left = 0。 給定已按升序排好序的 n個元素 a[0:n1]，現(xiàn)要在這 n個元素中找出一特定元素 x。因此這個問題滿足分治法的第一個適用條件 分析： 比較 x和 a的中間元素 a[mid]，若 x=a[mid]，則 x在 L中的位置就是 mid；如果 xa[mid]，由于 a是遞增排序的，因此假如 x在 a中的話， x必然排在 a[mid]的前面，所以我們只要在a[mid]的前面查找 x即可；如果 xa[i]，同理我們只要在 a[mid]的后面查找 x即可。再設(shè)將原問題分解為 k個子問題以及用 merge將 k個子問題的解合并為原問題的解需用 f(n)個單位時間。即將一個問題分成大小相等的 k個子問題的處理方法是行之有效的。 分治法的基本步驟 divideandconquer(P) { if ( | P | = n0) adhoc(P)。 hanoi(n1, c, b, a)。 由此可見， n個圓盤的移動問題可分為 2次 n1個圓盤的移動問題，這又可以遞歸地用上述方法來做。 當 n=1時，問題比較簡單。開始時，在塔座 a上有一疊共 n個圓盤，這些圓盤自下而上，由大到小地疊在一起。 在本例中，如果設(shè) p(n)為正整數(shù) n的劃分數(shù)，則難以找到遞歸關(guān)系，因此考慮增加一個自變量：將最大加數(shù) n1不大于 m的劃分個數(shù)記作 q(n,m)。 例 5 整數(shù)劃分問題 前面的幾個例子中，問題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。 當最大加數(shù) n1不大于 1時，任何正