33算法经典22题TSPNPC背包排工团等

1、一、设L为n元数组，其中的数已按增序排列，另给定数值 x,试采 用二分搜索技术设计算法，查找数值是否在 L中。要求若x在L中, 则输出j,使L(j)=x ;其x不在L中，则输出0。并证明，在最坏情 况下，对所有n元数组L(n>1)二分搜索算法将数值x与L中元素 比较次数为10g2 n 1。解：1、 11, r n2、if(1 r) j 0转 64、 if (x 1 ( j)转 65、if (x 1 (j)则 1 j 1,否则 r j 1,转 26、输出j ,结束比较次数：由于是2分搜索，每次比较或者成功，或者将搜索范围缩小一半。因此最多比较次数为 2的对数，又当n 1时，至少比较 1次，

2、所以比较次数不超过10g2n 1。二、满足三角不等式的TSP问题是否是NPC?为什么？解：证明思路，将哈密顿回路HC问题多项式变换到 TSP问题:HC TSP,且变换到TSP问题的实例是满足三角不等式的。因为HC NPC ,故满足三角不等式的TSP NPC。多项式变换：HC TSP设HC的实例为G ”及V1V2,Vm ,据此构造TS实例G (V,E),V V,(G必为完全图)，两个顶点之间的距离定义为1 i, j E di, j2 i,j E,并设TSP旅游界值为B m。易知这个变换是多项式的。若HC存在一条哈密顿回路，则这条回路在 G上的长度必为B,而B m是最短旅游的界值，故这条回路是满足

3、实例的一个 TSP旅游。若G存在一个满足B的TSP旅游，则该旅游必经过长度为1的边, 而这些边均在G上，因此这个TSP旅游在G上是一条HC回路。这样就将HC TSP ,而HC NPC。变换到的TSP实例的边长为1或2,可知该实例满足三角不等式，这就证明了满足三角不等式的 TSP问题是NPC问题。三、给定城市集合C Ci.Cn,任两城市距离 d(i,j),d(i,j) d(i,k) d(k,j),求最小货郎旅游。试证明满足三角不等式 的货郎优化问题为NP-hard。求满足三角不等式的TSP的近似算法， 并设计出能解答该问题的多项式时间近似算法A,其近似性能比为RA |0证明：即满足三角不等式的T

4、SP问题。证明思路，将哈密顿回路HC问题多项式变换到TSP问 题:HC TSP且变换到TSP问题的实例是满足三角不等式的(见第 1 题)。因为HC NPC ,故满足三角不等式的TSP问题是NPC问题。设存在TSP优化问题求解算法A,设计TSP判定问题的算法如下:对于给定TSP判定问题的实例：G，d，k,调用A(G，d),求得城市* *d(C i ,C i1) k排列：C1，C 2,若，则回答yes,否则回答no。若A为多项式算法，则上述算法能够在多项式时间内解答，故TSP判定问题可以图灵归约到 TSP优化问题，而已知 TSP判定问题是NPC的，所以TSP优化问题是NPH的。算法A：对G调用最小

5、支撑树(有权图权值之和最小的连通子图) 算法, 得到树T(V，Et)设T的奇数顶点为V1% 在G中求点集VlV2,的最小对集Ep e1©, E,将EP加入T中，形成欧拉图 在工中求欧拉回路V (1)V (2)，V (2m 2)V抄近路得到TSP：VVV (m)V证明Ra 2：因为TSP是回路，最小生成树是树，所以 d(T) OpT(l)又对于所有最小对集的两条边，d(Vi，vi 1)d(vi 2,vi 3)小于这四点相1连的最小TSP旅游距离2 ,133d(T1) d(T) -OPT(I) -OPT (I ) MM (I ) d(T1) - OPT (I)所以22,2三、假设一台处理

6、机可连续加工任务。 但在每个时刻，只允许加工一 个任务，含有待加工任务集合TT2,。其中所有任务都有相同的加工最早起始时间t1 t2tn 0,但它们所需要的加工时间 和加工最迟完成时间不同，即对于一个任务Ti T,其所需加工时间为Li ,加工最迟完成时间为 d i (1 i n)且Li Lj,di dj,(i j),试设计一个多项式时间算法，给出任务集合的排工表，使能按要求完成的任务数达到最大。要求证明你所设计算法的正确性，并分析其时间复杂性，并通过 下述实例说明算法的运行情况：T,T2 T 3 T 4 T5 T6,Li 6,L2 4,L3 3, L4 5L 7,L6 2;di 8,d29,d

7、3 10,d4 11,d5 16,d6 17;算法，将所有任务按其结束时间di由小到大排列，若满足1 i n时， 有di dj。令S空，S为排工表。 S S T1, k 1,m 1若k n,转设对k个任务，已经安排了 m个任务加工。L(s) L(T)。则对 Ti S第k 1个任务，只要有L(s) Lk1 dk1,则将其安排为第m 1个任务：即S S Tk 1, m m 1,k k 1,然后转若L(s) Lk 1 dk1,则从已安排的m个任务中，另择一个加工时间 最长的任务I,若Li Lk 1,则将I从S中移出，将I后的任务前移， 再把丁并入S, L(s) L(s) Lk 1 Li,k k 1

8、,转否则，k=k+1,转完成，S即排工表。正确性：由于di的排序是一定的，只需证明每一步操作都使加工时间 最短，则它的加工任务最多。归纳法证明:(1)当n 1时，显然成立；(2)假设n k(k 1)时正确，即若k个中拔下m个，且加工时间 最短，下面证明n k 1时也正确。当n k 1时，若L(s) Lk 1 dk 1 ,则安排第k 1个任务，显然k 1个 任务最多能安排m 1个，且时间最短；若L(s) Lk1 dk1 ,则由于算法中选择了 S中最长的任务且当 Li Lk 1时用Tk 1代替I ,使总加工时间L(s) Lk 1 Li L(s),故仍满足加 工时间最短，任务最多。综上所述，把n个任

9、务排完时，算法是正确的。复杂性：设有n个任务，则最坏情况下对每个加工任务都有 L(s) Lk1 dk1 ,从而从S中查找最长加工时间任务，则一次查找为 O(n),每个任务都查找为O(n2),排序加工任务为O(nlogn),因此总的 复杂度为O(n2)。算法的实例运行情况：d1 8,d2 9,d3 10,d4 11& 16,d6 17;L1 6,L2 4, L3 3,L4 5,Ls 7,L6 2;S=t1 k=1 m=1 Ls=6S=t2 Ls+L2=10>d2 Ti=t1,Li>L2,Ti out, T2 in k=2, Ls=4S=t2t3ls+L3=6<10, k

10、=3,m=2,Ls=6S=t2t3t4Ls+L4=11=d4,k=4,m=3,Ls=11 m=3S=t2t3t4Ls+l5=18>d5,Ti=T4,Li<L5,k=5,Ls=11S=t2t3t4t6Ls+L6=13<d6,k=6,Ls=13,m=4K=6,putout S=t2t3t4t6四、对于背包问题nmaxPiXin i 1 Xi 0,1 P,W( Z 1 i nWXj m i 1证明：(1)、当P NP时，该问题不存在多项式时间绝对近似算法(2)、背包问题存在绝对近似性能比 Ra 2的多项式时间近似算法 证明：(1)假设存在A,则存在常数(2):实例P P.Pn为价值

11、，W W1.Wn为重量，m Z为背包容量nmax PiXi 询问：求0,1向量X,使n i 1。WXi m i 1算法：将物体按照巴排序，使且 旦 康 WW W2Wn从1到n将物体装包，直到不能装为止，记其总价值和为GA(I)取 A(I) maxGA(I),maxP(Wi B) 1 i n复杂性：步骤O(nlog n),步骤O(n),故总的时间复杂性为O(nlog n)近似性能比：设GA(I)包含物体价值为PiP.，则P P2 . Pr Pr 1 OPT(I),而 A(I)rP,A(I) Max ,r故 2A(I)Pi Pmax OPT(I),i 1即 OPTin 2,Ra 2 A(I) n五

12、、n个整数a遇2,.an ,正整数m。求向量x1,x2,xnai 。i 1i 1证明是NPC的；若aaj ,求多项式时间算法，证明其正确性。j i六、给定WPAR问题实例：集合R ri,0，对于每个ri R有长度S(rJ Z*,1 i n。询问：是否存在子集R R,使S(ri) 因此，必存在R R使 S(ri) - S(ri)R2 R RS(ri)?ri R'2 ri RR'、试利用划分PAR是NPC问题，证明WPAR问题属于NPC类;(2)、试设计拟多项式算法：(a)判断R是否存在，(b)若存在，应给出一个满足询问条件的R。(3)、针对如下实例，说明你设计算法的执行过程R J

13、 , % , % , L , 1S ( ri)1,5,7,8.9解：(1)、证明WPAR是NPC证明：(将 PAR WPAR)设 PAR 实例为 A:为.4 , B S(a),73构造 WPAR 实例：:”2,.anbz,其中 4 7B,b2 -B若PAR中存在一个划分，使得 S(ai)-,则在 WPAR中， a2，B 7B 3-S(ai) bi 一 B 4B,而 S(ai) b2 B 2B。A22A A221若 WPAR 中存在 R R使 S(ri) S(n),则 S(r) 2B。R2 R RR分析元素构成，R中必含d不含“，而R R中必含bi ,不含b2。则有S(ri) b2旦，S(ri)

14、 bi B,即A中存在一个划分。R2 R R2又上述变换可在多项式时间内进行，因此PAR WPAR ,又PAR NPC ,因止匕 WPAR NPC(2)、设计WPAR拟多项式算法解：设BS(n),若B不能被3整除则无划分；若B能被3整除，则设计表t为n行，旦1列。3.T,前i个元素中有元素和为j","F,其它情况'若tn,与t ,则最终回答yes,否则no 3 ti,0 T t(1,j) T若 ti 1, j则 ti,j T若 ti 1, j S(ri) T ,则 ti, j T ti, 1 F t0, j F求解算法：记旦为b,记n a31、if (a 0或b 0

15、),则返回A为所求else if (ta 1,bT)2、a , go1 else3、将a加入集合b b S ai ;a , go1(3)、用设计算法求解实例R 1,5,7,8,9, B 30j： i01TT2TTTT3TTTTTT4TTTTTTT5TTTTTTTT七、给定2SAT问题实例，布尔变量集合 U u1,u2,.呜，项集合 C C1,C2,.Cn,Ci Xi,y u“2,.un U,?,1 i n,x,y 为 U 上布尔 变量字母。试设计多项式时间算法：（1）、判定2SAT实例是否有可满 足真值指派；（2）、若有可满足真值指派则算法给出使 C满足U的真 值指派。八、证明团问题属于NPC

16、思路：已知顶点覆盖VC NPC,而VC最大独立集问题，故最大独立 集问题 NPC （若V是G上的点覆盖，则V V是G上的最大独立集。 若V是G上的最大独立集，则V V是G上的点覆盖）。又最大独立集 问题 CL,故CL NPC （若V是G上的最大独立集，则V在G的补图Go 上所对应的子图是Go上的团）点覆盖：G上的最小顶点集合V , V覆盖G上所有的边；独立集：G上的点集合V , V中任两点之间无边；补图：Go V ,E ,V V, （? ? ?）团：G上最大完全子图九、TSP判定问题是数问题吗？是否存在拟多项式算法？为什么？答：TSP判定问题是数问题，因为任两城市间的距离d i,j及界值B 没

17、有任何约束。因为可以将 HC TSP,从而证明TSP NPC,而TSP有 限制1 d i,j 2,事实上d i,j 1或2,故不受限制的原始TSP问题 是强NPC。因此TSP问题不存在拟多项式时间算法。十、集合覆盖问题T实例： S s1s2,.sn, C C1C2,Cn, C 为子集族询问：求C C,使Ci S且C|最小Ci C求证：P NP时，上述问题无多项式时间绝对近似算法证明：若限制S 3q,Ci 3,Ci C,则集合覆盖问题变为X3C问题。而X3C NPC ,故集合覆盖问题是 NPC问题。(反证法)设存在多项式时间绝对算法 A,有A(I) OPT(I) k现将I复制K 1份到I ,易知

18、OPT (I ) (k 1)OPT(I),在I上应用算法AA(I )kA(I )k 1有 A(I ) OPT (I ) k, A(I ) (k 1)OPT(I ) k, OPT (I) 1,故： k1k 1OPT(I )(之所以取整，是因为集合覆盖问题是求最小值问题)因此可以构造算法A： (1)、I I ; (2)、对I调用A,得子集族的子集及A(I ) ； (3)、计算 如 即为实例I的最优解值OPT(I) k 1因为A是多项式的，所以A也是多项式的，这就多项式时间回答了集合覆盖问题。而我们已知集合覆盖问题是 NPC,这与P NP矛盾，故假设不成立。即不存在多项式时间绝对近似算法。十二、排工

19、问题(区间排工)实例：只有一台机器，n个任务，T,T2,.Tn。对于每任务有加工起始时间n ,终止时间di ,加工长度l询问：加工表(tj9),(tn),(tn)表示。的真正开始。使 (tk) r(tk)按时完成。i j 时，(ti)(tj) l(tj) , tj 在 ti 之前(tk) l(tk) d(tk)开始，或 (ti) l(tj) (tj) ,ti在tj之前开始。(两个任务不同时开始 进行)试证：(1)、问题NPC(2)、若限制ri r2 .rn r。，称为限制排工问题，试设计一多项式算法，限制排工任务数目最大，再证明算法的正确性，分析其复杂性。解：(1)见教材，试图将PAR区间排工

20、。 n设PAR实例A ai,a2an,对每一个a、有S0)均为整数,BS(a“。1 1根据PAR问题实例构造排工问题实例：T3',.3, E, r(ti) r(t2) r(tn)0BB 1d(ti) d(t2) . d(tn) B 1,L(ti) S(ai),r(E)- ,d(E) ,我们不考虑B为奇数的情况，因为B为奇数时，PAR不存在一 个划分。若PAR存在一个划分A,则可如此排工：将A中a、所对应的任务 ti安排在E之前完成，将A A所对应的任务安排在E之后完成。由 此排工问题存在一个排工。若排工问题存在一个排工，则可如此进行划分：将位于E之前的 任务t对应的ai置入集合A ,

21、E之后的任务所对应的a放在A A中。 由于E之前的任务加工长度为 旦 旦(B为偶数)，E之后的任务加2 2一一 一、，B 1BB工长度为B 1 B 1 ( 1)一, 而L(ti) ?(ai), 故222BS(ai)S(ai);,即PAR存在一个划分。ai Aai A A2因此，我们得 PAR区间排工，由于 PAR NPC ,故区间排工NPC。(2)、算法，将所有任务按其结束时间di由小到大排列，若满足1 i n时，有di dj。令S空，S为排工表。 S S T1, k 1,m 1若k n,转设对k个任务，已经安排了 m个任务加工。L(s) L(T)。则对 Ti S第k 1个任务，只要有L(s)

22、 Lk1 dk1,则将其安排为第m 1个任务：即S S Tk 1, m m 1,k k 1,然后转若L(s) Lk 1 dk1,则从已安排的m个任务中，另择一个加工时间 最长的任务I,若Li Lk 1,则将I从S中移出，将I后的任务前移， 再把丁并入S, L(s) L(s) Lk 1 Li,k k 1 ,转否则，k=k+1,转完成，S即排工表。正确性：由于di的排序是一定的，只需证明每一步操作都使加工时间 最短，则它的加工任务最多。归纳法证明：(3)当n 1时，显然成立；(4)假设n k(k 1)时正确，即若k个中拔下m个，且加工时间 最短，下面证明n k 1时也正确。当 n k 1 时，若

23、L(s) Lk 1dk1,则安排第k 1个任务，显然k 1个任务最多能安排m 1个，且时间最短；若L(s) Lki dki ,则由于算法中选择了 S中最长的任务且当 Li Lk i时用Tk i代替工，使总加工时间L(s) Lk i Li L(s),故仍满足加 工时间最短，任务最多。综上所述，把n个任务排完时，算法是正确的。复杂性：设有n个任务，则最坏情况下对每个加工任务都有 L(s) Lki dki ,从而从S中查找最长加工时间任务，则一次查找为 O(n),每个任务都查找为O(n2),排序加工任务为O(nlogn),因此总的 复杂度为O(n2)。ii十三、给定n个整数&户2,.an,满

24、足ai aj (超递增序列)，有一正 j in整数s,试设计算法A,找出一 n维0, I向量Xi.Xn,使得s aiXiii或无解。解：算法Assfor i n downto i doif s ai thenxi i; s s ai;elseXi 0;endifendforif s 0 then向量X %xn为答案 else 回答noendifi ii i证明：因为a aj,所以若ds ,必有aj s,故Xi应为1,否则ji使X1x全为1也没有正确答案复杂度：易知为O(n)。十四、(1)平面图的最大团问题有多项式时间算法吗？Why?答：有，因为当在平面图上考虑团问题时，任何平面图都不会含有多于

25、4个顶点的完全图，故只需检查所有的顶点个数，不超过4个子图 就能找到极大团。因4是常数，故子图数目是多项式有界的。所以必 有多项式算法。平面图的3着色问题有多项式算法吗？ Why?答：没有，因为我们可以设计一个转线轨道图，用局部替换技术将一 般图中的交点处理，将其转化为平面图。一般图的3着色问题NPC, 故平面图3着色也是NPC的，所以不存在多项式时间算法。十五、当P NP时，TSP优化问题是否存在Ra的多项式算法？答：不存在，用反证法证明。证明：设存在常数k ,使Ra k ,即存在算法A ,对TSP的任意实例G 有A(G) k*OPT(G)。设Gh (V,E)是哈密顿问题任意实例，由Gh构造

26、 TSP问题实例Gtsp如下。V(Gtsp) V(Gh) V1,(u,v) E(Gh)d(u,v)kv,(u,v) E(Gh)若 Gh 存在哈密顿回路，则 OPT(Gtsp) V , A(Gtsp) KOPT(Gtsp) kv 若 Gh 不存在哈密顿回路，则 OPT(Gtsp) V,A(Gtsp) OPT(Gtsp) kv 因此可以设计哈密顿问题的TSP实例，调用A算法由A(G) kV是否成立判定哈密顿是否存在解，又 A是多项式时间的，即哈密顿可以多项式时间求解，这与HC NPC矛盾。故假设不成立，TSP不存在Ra的多项式算法。十六、划分问题的拟多项式时间算法，并求划分的具体方案BS(ai)解

27、：设ai A ，若B为奇数，显然不能划分。若B为偶数，设一. T如果a.包括总价值为j的子集个布尔变量：(,)F其它情况t(n,力 T若 2，则回答yes,否则no计算。j) T的条件：若t(i 1，j) T,则 t(i，j) T若 t(i 1，j S(a。)T,则 t(i,j) T。0) T t(i， 1) F框图如右：B时间复杂度：外循环n,内循环3,故O(nB)。因为B的输入长度为 log2B,并不是输入长度的多项式，故不是多项式算法，是拟多项式 算法，O(nB) O(n210g2B)。十七、已知 MAXLA问题属于NPC类，MAXLA问题描述为实例：简单图G=(V, E)及正整数K。询

28、问：是否存在对应映射 P:A1,2，.，|V|,使 |P(u) P(v)| K?(u,v) E试证明MINLA问题也属于NPC类，MINLA问题为实例：与MAXLA相同询问：是否存在对应映射 P:VJ1,2,.,|V|,使 |P(u) P(v)| K?(u,v) E证明：试图将MAXLA MINLA设图G(V,E)及正整数k为MAXLA的实例，定义MINLA的实例为图G (V ,E)其 中 V V,E (u,v)|u v,(u,v) E.n(n2 1)6n(n 1)( n 1) kk,即G为G的补图。对顶点集合V中所有可能的映射P,考虑：固定一点i与其它所P(u)固定顶点 i , P0) P(

29、j)P(i)P(u)P(v)P(i) - 11i(ni)P(i)u,v V u vn 12 ii 1n(n 1)(2n 1) 1n(n 61)又G与G互为补图P(u)所以(u,v) eP(v)n(n2 1)P(u) P(v)(u,v) EP(u)(u,v) EP(v)|P(u)所以(u，v) eP(v)|K当且仅当|P(u)(u,v) EP(v)| 吗6所以MAXLAMINLAMINLA NPC十八、用图灵归约技术证明k个最大子集 NP HARDk个最大子集问题:实例：Ae但.%, n个元素,S(a) Z* ,每个元素有一个长S(q) Z*o两个非负整数B S(a)和k 2 A a A询问：A

30、中是否有k个不同的子集A Ao满足S(A) S(a) B且S(A) B, a A A,其中 S(A) S(a) a A证明：假设SA,S,B,K是解k个最大子集问题的子程序，其中A 电an，长度函数S：A Z ,B S(A),k 21A设集合A ai，a2an和长度函数S:A Z是划分问题的任意实例。设计划分问题的算法。从计算S(A)开始，若S(A)是奇数，则回答NO。b S(A)否则 工，并调用子程序SA，S，B，K算法A：若S(A)为奇数，则划分问题回答NO,结束。b2置 2 ,调用算法B算法B：求满足S(A) b，S(A) S(a) b，a A A的子集A的最大数目L*。Lmin 0,L

31、max 2n , ( L可能的界限) *若Lmax Lmin 1 ,则L Lmin并结束。L(Lmax /。)/2；调用SIASbU ,检查是否有L个子集A满足S(A) b若回答YES,则扁 L，转若回答NO ,则Lmax L,转根据求出的满足S(A) b的子集A的最大数目L*,调用一次_ _ *SA,S,b 1, L若回答 YES,则表明所有满足S(A) b的子集A ,也都满足S(A) b 故相应划分问题回答 No若回答NO ,则满足S(A) b的子集一定存在，所以划分回答Yes。十九、排工问题大全1、区间排工实例：有限任务集合T ti,t2,.tj,r(tk)最早开始时间，d(tk)最晚结

32、 束时间，l(tk)加工长度。询问：是否存在排工表(tk) k 1,2n(1)区间排工 NPC,用划分 区间排工区间排工强NPC证明：将3划分区间排工设三划分实例为A a1，a2备a3m), S(ai) Z,B Z由此构造区间排工实例：T A t1,tm i), L(ti) 1,i 1.m 1, L(ai) S(a),i 1.3m, r(ti) iB ir(ai) 0, d (ti) iB i, d (ai) mB m 1若三划分问题回答yes,变换后的区间排工也回答yes。若区间排工回答yes,则三划分问题也回答yes。且该变换是拟多 项式变换。因为：三划分 强NPC,所以：区间排工强NPC

33、2、最小迟序排工，有半序关系和最晚结束时间，不能按时完成的任务k,证明 NPC,用CL证明。3、先行约束排工：L为1,处理机为m ,半序关系(1)没有半序或半序为树时是 P问题(2) m 1or2日寸是P问题4、多任务排工实例：m个处理机Pi,P2,Pm处理任务T 我.tn,加工时间u(ti),任务之间有半序关系。询问：最短时间内完成NI(I,L) 2 2(1) OPT(I) m (任意主次表，有空就加工)，非空闲算法算法：开始所有处理都空闲，所有任务都未加工对任务主次表从左向右扫描，判定每个任务 tj是否处于加工状态。若可加工，则安排至下标最小的空闲处理机上加工 任务主次表是按半序关系的。N

34、I(I,L) c 1 2 -证明OPT(I) m将N(I ,L)的时间区0,N(I, L)分成两部分：A每个区间所有机器都空 闲B至少有一台机器空闲B 1. J显然k不相交则在半序关系中存在一条通路ti1,t2,.%,该通路覆盖子区间1 . kl所以：OPT (I) u(tj) j 1ku(j 1j)OPT(I)1 nu(tij)m j 1NI(I,L)1 n一(u(tj)m j 1(mk1) u(i 11 n m 1 i) u(tj)m j 1mku( i) OPT(I) i 1OPT (I)即 NI (I,L)注：当最大加工时间D,限制m 2,D 13)时，变成PAR问题2ai A5、独立

35、任务排工实例：任务T1T2,.丁一加工长度1也,.储(1) LPT算法，先排时间长的. LPT(I). OPT(I)4 13 3m将任务排序，形成加工主次表L Ti,T2,.Tn, ti t2tn对主次表从1到n扫描，若有空闲机器，则将任务安排空闲机器上加工，直至完成。复杂度：O(nlogn),多项式算法证皿42：OPT (I)3 3m当m 1时，显然成立。当m 1时，假设最后完成的任务为tn。若最后完成的任务是tk,则只考虑前k个任务，若前k个满足，则n个当然满足在0,LPT(I) tn内所有任务都非常空闲n 1LPT(I) tn t -i 1 mLPT (I)一tim i 1tn1 n又

36、OPT (I)tim i 1LPT(I) 1 m JtnOPT (I) m OPT (I)若OPT (I) 3tn,则每个机器上最多安排 2个任务，这样的排工是最优的，当然满足;若0PT(I)竟,则副4 13 3m综上得证(再举例说明上界不能小于 3)(2) F算法：多项式近似方案:F1 _1LOPT(I) 1 2将任务从大到小时间排序:T Ti,T2,.Tn确定正整数k,对前k个任务，求最优先排工，后n k个按 先大后小顺序排工。证明：设T是前k个任务的排工时间,若F(I) T,则OPT(I) F(I ), 设 F(I) T。在0,F(I) tki区间所有的处理器非空闲，tki开始做时，其它

37、有 任务可能未做完。 nti m(F(I) tki) tk i i 11 nm 1OPT(I ) ti F(I) tk 1 m i 1m又，至少有一台机器加工了 tk1和前k个任务的平均个数，即1 -m个任务；又，tk1是前k 1个中最小的。kOPT(I) (1- )tk 1mm 1m 11F (I )1 m tk 11 m tk 11 mOPT (I) OPT (I)1 点 tk1 1 寺算法复杂度：TA(m,n) O(mk nlog n)二十、装箱问题实例：n个物体集合，S ai,a2an,每个物体a S,体积为W(ai), 容量为C的箱子。询问：需要多少个箱子才能全部装完首次适合算法Fi

38、t-First:剧2算法：按照一定顺序依次装入箱子。O(n)。证明：任意两个相邻箱子Bi上装入物体体积大于c,B1.Bk,n若 FF(I)为偶数,则 2 W(ai) C FF(I)；又,i 1nW(ai) C OPT (I) i 1FF (I) 2OPT (I)n若 FF(I)为奇数，则 2 W(ai) C (FF(I) 1),i 1FF(I ) 2OPT(I ) 1又，FF(I),OPT(I)为整数，OF* 2(2) FD算法，先大后小将物体排序，体积从大到小依次装箱,11FD(I) OPT(I) 49卜一、背包问题实例：有限集合 UUi,U2,.Un, S(u)Z为重量,W(u) Z为价值

39、判定问题：是否存在UU,S(Ui)Ui UB, V(Ui)Ui UMaxPiXi优化问题:,求向量不.%。nXiWi Mi 1(1)、判定问题 NPC限制 S(u)为偶数，S(u) V(u)B k 1 S(uJ ,则上述问题变为 u u2 ui uPAR 问题。 PAR NPC,背包 NPC。(2)、背包问题无多项式时间绝对近似算法，将价值扩大k 1倍，变成另一个问题。反证法.(3)、Ra(I) 2的A算法(见前文)*，(4)、多项式近似方案： 1 ,证明这个公式，要求给出时间Pmax1 k复杂度算法描述：对任意一种k个元素的组合都先放入包中尝试，最后选择一个最好的尝试。伪代码：k)Procedure approx (P,W, M , n, k) /(价值、重量向量、重量 限制、元素个数、 Pmax 0for all combinatio ns I of size k and weight M do Pi P i IPmax max Pmax, P L(I, P,W, M , n) /L()子程序 end forend下面算法先装k个再继续装：Procedure L(I,P,W,M