《背包和subsetsum问题的近似解》由会员分享，可在线阅读，更多相关《背包和subsetsum问题的近似解（11页珍藏版）》请在金锄头文库上搜索。
1、背包问题的近似解一、背包问题的数学描述给定整数C和2个整数序列(s1,s2,sn) (p1,p2,pn) 。 s1,s2,sn以非递增的顺序排列 。设N=(1,2,n)为下标集,求：受限于：问题的简化版给定整数C和整数序列(s1,s2,sn) ，设 (1,2,n)为下标集,求:受限于：二、背包问题的简单近似算法sKnapk(C,S,take)int maxSum,sum;indexSet T = new IndexSet;int j;take =; maxSum = 0;for each subset TN with at most k elements:sum =iT si; if (sum
2、C)for each j not in T:if (sum+ sj C)sum+= sj;T=Tj;if (maxsum0,算法sKnapk 做 O(knk+1)次运算； sKnap0做(n) 次运算。所以对k0 ，sKnapk P证明：N包含j个元素的子集共有Cnj个，所以外循环做 次运算 。因为Cnjnj，所以:加上内循环的至多n次的复杂性，算法的复 杂性为O(knk+1+n)。定理13.13定理：对k0,RsKnapk (m) 和SsKnapk (n)在最坏情况 下至多为1+1/ k。设输入I为(s1,s2,sn) ，opt(I )=m(最优解情 况下，背包内所含物体的size总和)。若 (si1,si2,sip) 是所得到的装填背包的 最优解。若pk,则最优解也应在近似算法的范围 内。若pk,则最优解(si1,si2,sip)以非递增的次 序排列。 因为: m=si1+si2+sip 1jp sij m/j si(k+1) m/(k+1) 1jp sij m/j根据近似算法，如果j 是最优解中k 之后第一 个不能被加进val(sKnapk(I)的object: val(sKnapk(I)+sjCm val(sKnapk(I) m- m/j m- m/(k+1)即：近似解mk/(k+1) Rm/mk/(k+1)=1+1/k
