【正文】 } } )n(O)n(O)1mn(m)n(Om3n2mn2mmn0i??????? ??? ??? 0/1背包 問題描述 問題 已知一個(gè)載重為 M的背包和 n件物品 ， 物品編號(hào)從0到 n1。 計(jì)算所有 Sj和 S1j的步驟如下： S1={(0,0)}， 函數(shù) f(1,X)只有一個(gè)階躍點(diǎn)； S1j={(X,P)|(Xwj,Ppj)?Sj?1， 也就是說(shuō) ， 由集合 Sj1中的每個(gè)階躍點(diǎn) （ X,P） ， 得到集合 S1j中的一個(gè)階躍點(diǎn) （ X+wj,P+pj） ； Sj是合并集合 Sj1?S1j， 舍棄其中被支配的階躍點(diǎn)和所有 XM的階躍點(diǎn)得到 。 (X2,P2)=(X+wn－ 1,P+pn－ 1)， 其中 (X,P)是 Sn1 中 使得 X+wn－ 1?M的最大的階躍點(diǎn) 。 設(shè)一條流水線上有 n 個(gè)作業(yè) J={J0,J1,… ,Jn?1} 和 m 臺(tái)設(shè)備P={P1,P2,… ,Pm}。 完成時(shí)間 F(S)是所有作業(yè)都完成的時(shí)間 。 流水作業(yè)調(diào)度問題要求確定這 n個(gè)作業(yè)的最優(yōu)加工順序 ，使得從第一個(gè)作業(yè)在設(shè)備 P1上開始加工 ， 到最后一個(gè)作業(yè)在設(shè)備 P2上加工完成所需的時(shí)間最少 。 設(shè) ? =(?(0),?(1),?(2),?(3))是最優(yōu)作業(yè)排列 。 【 程序 7－ 12】 Johnson算法 struct Triplet{ int operator (Triplet b)const { return t。d[i].t=a[i]。i++) if(d[i].ab==0) c[left++]=d[i].jobNo。 for(i=1。 if(thissumsum){ sum=thissum。 for(i=1。 bestj=j。 ???????????????????nnkkninnikknijikk asasnjnniaC121222211 m a xm a x12,21,.int MaxSubSum(int a, int left, int right) { int sum=0。i=left。 if (rightss2) s2=rights。 b=0。 jnjjikkjinjjkknjijikkjijbaanjab????????????????????????????111111m a xm a xm a xm a x1m a x 為，則所求的最大子段和，若記。i=n。 if (sumleftsum) sum=leftsum。 if (leftss1) s1=lefts。 else{int center=(left+right)/2。 ?? ?????1jikkjjikk aaa2. 分治方法求解 ? 從問題的解的結(jié)構(gòu)可以看出，它適合于用分治策略求解： ? 如果將所給的序列 a[1:n]分為長(zhǎng)度相等的兩段a[1:n/2]和 a[n/2+1:n]，分別求出這兩段的最大子段和，則 a[1:n]的最大子段和有三種情形： A. a[1:n]的最大子段和與 a[1:n/2]的最大子段和相同； B. a[1:n]的最大子段和與 a[n/2+1:n]的最大子段和相同； C. a[1:n]的最大子段和為下面的形式 。i++){ int thissum=0。 bestj=j。i++) for(j=1。 } Johnson算法的時(shí)間取決于對(duì)作業(yè)集合的排序，因此，在最壞情況下算法的時(shí)間復(fù)雜度為 O(nlogn)，所需的空間復(fù)雜度為 O(n)。d[i].ab=1。 }。 所以最優(yōu)解為： (?(0),?(1),?(2),?(3)) ＝（ 0,2,3,1）。 動(dòng)態(tài)規(guī)劃法求解 在兩臺(tái)設(shè)備的情況下 ， 存在一個(gè)最優(yōu)非搶先調(diào)度方案 ， 使得在 P1和 P2上的作業(yè)完全以相同次序處理（ 若 m2則不然 ） 。 OFT表示指非搶先調(diào)度最優(yōu)完成時(shí)間 POFT表示搶先調(diào)度最優(yōu)完成時(shí)間 。 設(shè)第 i個(gè)作業(yè)的第 j項(xiàng)任務(wù) Tji所需時(shí)間為 tji， 1?j?m，0?in。 If (P2P1) xn－ 1=1。P,int *x) { S－ 1={(0,0)}。所謂 0/1背包問題是指在物品不能分割 ， 只能整件裝入背包或不裝入的情況下 ， 求一種最佳裝載方案使得總收益最大 。i=nm。 c[i][i+1]=q[i]+q[i+1]+p[i+1]。k=m。 ? ?? ???n1in0i1)i(q)i(p 動(dòng)態(tài)規(guī)劃法求解 設(shè) c(0,n) 是由元素值集合 {a1,… ,an}所構(gòu)造的最優(yōu)二叉搜索樹的代價(jià) ， 則 n)w ( 0 ,} n)c ( k ,1)kc ( 0 , { m i n} n)c ( k ,1)kc ( 0 ,n) w ( 0 ,{ m i n n)c ( 0 ,nk1nk1????????????一般地 ， c(i,j) ,i?j 是元素值集合 {ai+1,… ,aj}所構(gòu)造的最優(yōu)二叉搜索樹的代價(jià) ， 設(shè) r(i,j)=k為該樹的根 ，要求結(jié)點(diǎn) k滿足 )jw (i ,} j)c (k ,1)kc (i , {m i n} j)c (k ,1)kc (i ,j){ w ( i , m i nj)c (i ,jk1ijk1i??????????????例 7－ 7 設(shè) n＝ 4且 （ a1,a2,a3,a4） =(Mon,Thu,Tue,Wed)。 k++) { int t=LookupChain(i,k)+LookupChain(k+1,j) +p[i]*p[k+1]*p[j+1]。 } 例 7－ 5 6個(gè)矩陣連乘積 A0A1A2A3A4A5， 設(shè)它們的維數(shù)分別為 A:30?35， B:35?15 C:15?5 D:5?10， E:10?20，F(xiàn):20?25。if(s[i][j]+1j) cout39。} if (is[i][j]) cout39。k++) { int t=m[i][k] +m[k+1][j]+p[i]*p[k+1]*p[j+1]。 r=n。 …… private: