![](https://iknow-base.cdn.bcebos.com/lxb/notice.png)
近似算法的子集和问题的近似算法
问题描述:设子集和问题的一个实例为〈S,t〉。其中,S={x1,x2,…,xn}是一个正整数的集合,t是一个正整数。子集和问题判定是否存在S的一个子集S1,使得∑x = t。(x属于S1)
1 子集和问题的指数时间算法
int exactSubsetSum (S,t)
{
int n=|S|;
L[0]={0};
for (int i=1;i<=n;i++) {
L[i]=mergeLists(L[i-1],L[i-1]+S[i]);
删去L[i]中超过t的元素;
}
return max(L[n]);
}
算法以集合S={x1,x2,…,xn}和目标值t作为输入。算法中用到将2个有序表L1和L2合并成为一个新的有序表的算法mergeLists(L1,L2)。
2 子集和问题的完全多项式时间近似格式
基于算法exactSubsetSum,通过对表L[i]作适当的修整建立一个子集和问题的完全多项式时间近似格式。
在对表L[i]进行修整时,用到一个修整参数δ,0<δ<1。用参数δ修整一个表L是指从L中删去尽可能多的元素,使得每一个从L中删去的元素y,都有一个修整后的表L1中的元素z满足(1-δ)y≤z≤y。可以将z看作是被删去元素y在修整后的新表L1中的代表。
举例:若δ=0.1,且L=〈10,11,12,15,20,21,22,23,24,29〉,则用δ对L进行修整后得到L1=〈10,12,15,20,23,29〉。其中被删去的数11由10来代表,21和22由20来代表,24由23来代表。
对有序表L修整算法
List trim(L,δ)
{ int m=|L|;
L1=〈L[1]〉;
int last=L[1];
for (int i=2;i<=m;i++) {
if (last<(1-δ)*L[i]) {
将L[i]加入表L1的尾部;
last=L[i];
}
return L1;
}
子集和问题近似格式
int approxSubsetSum(S,t,ε)
{ n=|S|;
L[0]=〈0〉;
for (int i=1;i<=n;i++) {
L[i]=Merge-Lists(L[i-1],
L[i-1]+S[i]);
L[i]=Trim(L[i],ε/n);
删去L[i]中超过t的元素;
}
return max(L[n]);
}