1問題描述n個作業(yè){1，2，…，n}要在由2臺機器M1和M2組成的流水線上完成加工，每個作業(yè)加工的順序都是先在M1上加工，然后在M2上加工，M1和M2加工作業(yè)i所需的時間分別為ai和bi。流水作業(yè)調度問題要求確定n個作業(yè)的最優(yōu)加工順序，使得從第一個作業(yè)在機器M1上開始加工，到最后一個作業(yè)在機器M2上加工完成所需的時間最少。流水作業(yè)調度（p72）2問題分析一個最優(yōu)調度應使機器M1沒有空閑時間，且機器M2的空閑時間最少。一般情況下，機器M2上會有機器空閑和作業(yè)積壓兩種情況。積壓不要緊盡量別閑著設全部作業(yè)的集合為N={1，2，…，n}。S

N是N的作業(yè)子集。在一般情況下，機器M1開始加工S中作業(yè)時，機器M2還在加工其他作業(yè)，要等時間t后才可利用M2。將這種情況下完成S中作業(yè)所需的最短時間記為T(S,t)。t是M1開始加工S時，M2加工其它作業(yè)還需要的時間。等待時間不算在t里面。“才可利用”的意思是M2可以利用（空閑），但不一定利用。流水作業(yè)調度流水作業(yè)調度S不同加工順序，所用時間不同，最短時間標記為T(S,t)當S=N時，如何表示？3

M1M2SStT(S,t)4最優(yōu)子結構性質設

是n個流水作業(yè)的一個最優(yōu)調度，所需的加工時間為a

(1)+T’。其中T’是機器M2等待時間b

(1)及完成其它作業(yè)

(2)，…，

(n)所需的時間。a

(1)+T’時間最短。是否除去(1)后的調度方案也是最優(yōu)方案？記S=N-{

(1)}，則有T’？=T(S,b

(1))。由T的最優(yōu)性可知，T’

T(S,b

(1))。若T’>T(S,b

(1))，設

’是作業(yè)集S在機器M2的等待時間為b

(1)情況下的一個最優(yōu)調度。則

(1)，

’(2)，…，

’(n)是N的一個調度，這個調度所需的時間為a

(1)+T(S,b

(1))<a

(1)+T’。這與

是N的最優(yōu)調度矛盾。故T’

T(S,b

(1))。從而T’=T(S,b

(1))。即流水作業(yè)調度問題具有最優(yōu)子結構的性質。流水作業(yè)調度5流水作業(yè)調度5

M1M2S=N-{Π(1)}St=bΠ(1)T(S,t)aΠ(1)T’6遞歸結構由流水作業(yè)調度問題的最優(yōu)子結構性質可知：利用其子結構性質，對集合中的每一個作業(yè)進行試調度，在所有的試調度中，取其中加工時間最短的作業(yè)做為選擇方案。流水作業(yè)調度7遞歸結構由流水作業(yè)調度問題的最優(yōu)子結構性質可知：T(S,t)中的bi+max{t-ai,0}：

當選定作業(yè)i為S中第一個加工作業(yè)之后，在機器M2上，作業(yè)i必須在max{t,ai}時間之后才能開始i。即機器M2上開始對S-{i}中的作業(yè)進行加工之前，所需要的等待時間為：

bi+max{t,ai}–ai

=bi+max{t-ai,0}

注：若t>ai

，則作業(yè)i在M1上加工完畢（用時ai）之后，還要再等t-ai個時間單位才能開始在M2上加工；若t≤ai

，則作業(yè)i在M1上加工完畢之后，立即可以在M2上加工，等待時間為0。流水作業(yè)調度8流水作業(yè)調度

M1M2SStT(S,t)aibiS-{i}9流水作業(yè)調度

M1M2SStT(S,t)aibiS-{i}流水作業(yè)調度根據(jù)上述遞歸式，可設計出解流水作業(yè)調度問題的動態(tài)規(guī)劃法分治法子問題規(guī)模？階乘n！動態(tài)規(guī)劃法子問題規(guī)模？2n-1改進策略（自學）流水作業(yè)調度的Johnson法則時間復雜度O(nlogn)空間復雜度O(n)1011電路布線(P70)問題描述在電路板的上、下兩端分別有n個接線柱。根據(jù)電路設計，要求用導線(i,π(i))將上端接線柱與下端接線柱相連，其中π(i)是{1,2,…,n}的一個排列。導線(i,π(i))稱為該電路板上的第i條連線。對于任何1≤i<j≤n，第i條連線和第j條連線相交的充要條件是π(i)>π(j)。電路布線問題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。即該問題要求確定導線集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。應用背景：印刷電路板的制作飛線？12最優(yōu)子結構性質記 ，N(i,j)的最大不相交子集為MNS(i,j)，Size(i,j)=|MNS(i,j)|。

i，上端最大接線柱；j，下端最大接線柱當i=1時，當i>1時：j<π(i)，此時，。故N(i,j)=N(i-1,j)，從而Size(i,j)=Size(i-1,j)。電路布線})(,,))(,(|{),(jtitNetstttjiN￡￡?=pp13電路布線j≥π(i)若(i,π(i))∈MNS(i,j)。則對除(i,π(i))外的任意(t,π(t))∈MNS(i,j)有t<i且π(t)<π(i)。在這種情況下MNS(i,j)-{(i,π(i))}是N(i-1,π(i)-1)的最大不相交子集。即Size(i,j)=Size(i-1,π(i)-1)+1。若，則對任意(t,π(t))∈MNS(i,j)有t<i。從而。因此，Size(i,j)≤Size(i-1,j)。另一方面，故又有Size(i,j)≥Size(i-1,j)，從而

Size(i,j)=Size(i-1,j)。由上述分析可知，問題具有最優(yōu)子結構性質。14電路布線遞歸結構電路布線問題的最優(yōu)值為Size(n,n)。(1)當i=1時(2)當i>1時算法設計－P71-7215問題描述給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?在裝入背包時，每種物品i只有兩種選擇：裝入或者不裝入。既不能裝入多次，也不能只裝入一部分。因此，此問題稱為0-1背包問題。0-1背包問題(P75)160-1背包問題最優(yōu)子結構性質設(y1,y2,…,yn)是所給0-1背包問題的一個最優(yōu)解，(y2,…,yn)是否是下面對應問題的最優(yōu)解？反證法：設(z2,…,zn)是最優(yōu)解，(y2,…,yn)不是最優(yōu)解。(y1,z2,…,zn)比(y1,y2,…,yn)更優(yōu)，矛盾170-1背包問題遞歸結構設所給0-1背包問題的子問題：

的最優(yōu)值為m(i，j)，即m(i，j)是背包剩余容量為j，可選擇物品為i，i+1，…，n時0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結構性質，可以建立計算m(i，j)的遞歸式如下：18算法描述在處理細節(jié)上的方法，與電路布線算法完全相同。knapsack算法需要O(nc)計算時間，traceback算法需要O(n)計算時間。算法假定物品重量wi都是整數(shù)，表示背包容量的變量j，是以1為單位的。當背包容量較大時，算法需要的計算時間較多。Wi非整數(shù)和克服背包容量大時計算時間較多問題有相應的算法改進（感興趣者自學）0-1背包問題圖像壓縮問題描述（P67）：

在計算機中，常用像素點的灰度值序列{p1,p2,……pn}表示圖像。其中整數(shù)Pi，1≤i≤n，表示像素點i的灰度值。通常灰度值的范圍是0—255，因此最多需要8位表示一個像素。

壓縮的原理：對序列{p1,p2,……pn}設斷點，將其分割成一段一段的。分段的過程就是要找出斷點，讓一段里面的像素的最大灰度值比較小，那么這一段像素(本來需要8位)就可以用較少的位(比如7位)來表示，從而減少存儲空間。

b代表bits,l代表length,

b[i]表示第i段一個像素點需要的最少存儲空間(少于8位才有意義)，l[i]表示第i段里面有多少個像素點。如果限制1≤l[i]≤255,則需要8位來表示l[i]。而b[i]≤8，需要3位表示b[i]。所以每段所需的存儲空間為l[i]*b[i]+11位。假設將原圖像分成m段，那么需要位的存儲空間。

圖像壓縮問題就是要確定像素序列{p1,p2,……pn}的最優(yōu)分段，使得依此分段所需的存儲空間最小。圖像壓縮問題描述：設l[i],b[i],1≤i≤m是{p1,p2,……pn}的一個最優(yōu)分段則l[1],b[1]是{p1,……,pl[1]}的一個最優(yōu)分段且l[i],b[i],2≤i≤m是{pl[1]+1,……,pn}的一個最優(yōu)分段。（顯而易見，反證法）即圖像壓縮問題滿足最優(yōu)子結構性質。圖像壓縮最優(yōu)子結構性質：圖像壓縮遞推關系：

設s[i],1≤i≤n是像素序列{p1,……pi}的最優(yōu)分段所需的存儲位數(shù)，則s[i]為前i-k個的存儲位數(shù)加上后k個的存儲空間。由最優(yōu)子結構性質可得：式中多邊形游戲（P64，自學）23多邊形游戲（自學）24多邊形游戲（自學）25多邊形游戲（自學）2627最優(yōu)二叉搜索樹（P80）二叉搜索樹若左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值；若右子樹不空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值；它的左、右子樹也分別為二叉搜索樹。問題描述S＝｛x1,x2,……,xn｝是升序集，對應的二叉搜索樹中，內部結點存儲S中的元素，葉子結點是類似(xi,xi+1)的開區(qū)間。28最優(yōu)二叉搜索樹在S的二叉搜索樹中搜索元素x，返回結果可能存在兩種情況：樹的某個內結點x＝xi，對應的概率為bi。在葉子結點中確定x∈(xi,xi+1)，對應的概率為ai。x0=-∞，xn+1=+∞。(a0,b1,a1,……,bn,an)稱為集合S的存取概率分布。29最優(yōu)二叉搜索樹在S的二叉搜索樹T中，設存儲元素xi的結點深度為ci，葉子結點(xj,xj+1)的結點深度為dj，則： 表示在二叉搜索樹中進行一次搜索需要的平均比較次數(shù)，又稱為T的平均路長。一般情況下，不同的二叉搜索樹的平均路長是不同的。最優(yōu)二叉搜索樹問題要求對于有序集S及其存取概率分布(a0,b1,a1,……,bn,an)，在所有表示S的二叉搜索樹中找出一棵具有最小平均路長的二叉搜索樹。30最優(yōu)二叉搜索樹最優(yōu)子結構性質二叉搜索樹T的一棵含有結點xi，……，xj和葉子結點(xi-1,xi),…,(xj,xj+1)的子樹，其存取概率為：

其中，

31最優(yōu)二叉搜索樹設Tij是有序集{xi，…，xj}關于存取概率的一棵最優(yōu)二叉搜索樹，其平均路長為pij，且根結點為元素xm，則其左、右子樹Tl、Tr是關于集合{xi，…，xm-1}和{xm+1，…，xj}的最優(yōu)二叉搜索樹（反證法），其