资源描述：
《算法分析与设计2006第e讲》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、上次内容：(1)图着色不能多项式时间近似到小于，TSP问题不能多项式时间近似到任意常数。(2)，时间复杂度O(mK+nlogn)，K越大求解优化程度越高，1+e，T=O()。M是常数时可以认为是多项式时间近似方案。什么是多项式时间近似方案：定义7.2：若问题p的近似算法A(e)若满足对任意实例I任意e>0(1)RA(e)[I]<1+e；(2)A(e)的时间复杂度是I输入长度的多项式函数。则A(e)称为求解问题p的多项式时间近似方案。解释：(1)1+e很容易说明，但后面的多项式需要解释,时间复杂度一定与e有关。
2、近似性能比1+e，时间复杂度为：O()，O(n)，O(n2)，PTAS。特殊情况：O()等等，各种情况。一定是e越小，时间复杂度越大。最后一种情况又称为完全多项式时间近似方案。FPTAS完全多项式时间近似方案：近似度1+e；时间复杂度：P(n,)，P(·,·)是多项式函数。(2)为什么叫多项式近似方案，而不叫多项式近似算法。因为e没有确定大小，只有程序运行时才能确定。再考虑背包问题：设计真正的多项式时间近似方案。，xiÎ{0,1},I=1,…,n设元素：a1,a2,…,an
3、p1,p2,…,pn
4、w1,w2,
5、…,wn(1)简单算法描述先挑k个元素放入背包，然后调用前面7.1节算法选择其他元素装包。两种规则，价值重量比大者优先；价值大者优先，二者择优选一为最终解。这样装法显然不一定多么好，若对任意一种k个元素的组合都先放入背包尝试，则最后结果一定比直接装入好。全部尝试完后选择最好的，作为最后结果。算法描述：Proceduree-approx(P,W,M,n,K)1Pmax=0;2forallcombinationsIofsize£Kandweight£Mdo//不超过K元素的组合3PI=;4Pmax=max{Pma
6、x,PI+L(I,P,W,M,n)}//L(I,P,W,M,n)是子程序。用于计算剩余容量装包。5endfor6end下面这个算法是先试装k个后再继续装ProcedureL(I,P,W,M,n)//I是已经装入的元素集合(1)S=0;T=M-;IS=Æ(2)Fori=1tondo(3)IfiÏIandWi£Tthen(4)S=S+Pi;T=T-Wi;IS=IS+{i}(5)Endif(6)EndforReturn(max{S,max{Pi
7、iÏI,1£i£n}})//S是由第一种策略装进包的，后面是第二种策略
8、装进包的，比较取优。End例子：n=8，M=110。P1P2P3P4P5P6P7P81121313343535565111212333434555上面已经按照价值重量比排好序了。(1)K=0时，直接从头开始装入：x1,x2,x3,x4,x5,x6,x7,x8=11111000，前5个装入背包Pmax=11+21+31+33+43=139W=1+11+21+23+33=89(2)K=1，时，先装入1个，再装入其他，得到1,2,3,4,7最好x1,x2,x3,x4,x5,x6,x7,x8=11110010Pmax
9、=11+21+31+33+45=151W=1+11+21+23+45=101(3)k=2，先装入2个，再装入其他，得到1,2,3,5,6最好x1,x2,x3,x4,x5,x6,x7,x8=1,1,1,0,1,1,0,0Pmax=11+21+31+43+53=159W=109=1+11+21+33+43这是最优解。定理7.15设背包问题最优解为P*，Pmax是前述先装算法e-approx得到的解，则对任意背包问题实例均成立。证明：//为什么会很好呢？因为有可能将最优解前K个价值最大的先装入。(1)给定实例，设R
10、是该实例最优解的装入背包元素下标集合，若
11、R
12、£K，则能够求到最优解，以下假设
13、R
14、>K。(2)将R中的元素的价值重量写成有序对，按照以下规则重新排序：(),(),…,()
15、
16、(),…,()。(*),…,是R中元素前k个最大价值，³…³³，1£j£
17、R
18、-k。(*)从i=k+1开始按照价值重量比排序³…³。(3)考虑先将R中前K个元素装入背包的情况，有一种这样情况。PI=设S是调用L(I,P,W,M,n)增加的收益。会不会将R中元素全部装入包？则：P*19、背包的R中元素的价值。这一步特别关键，要找一个比P*还好的界限，要说明白。为什么，因为装入以后就超重了。还是很难说明的。为什么放进背包别的东西了，因为那些元素价值重量比更大。如果将同样重量，不属于最优解的元素替换出来，一定使价值变小。Pmax³PI+L，这仅是一种情况得到装包收益为PI+S，算法是所有情况都试遍得到的解，结果不会比这次差。，m>k,S³，Pmax³(K+1)所以前面的不等式成立。没有
