近似演算法T

A. 近似演算法的子集和問題的近似演算法

問題描述：設子集和問題的一個實例為〈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])；
}