子集和问题近似算法.cpp

自己编写的子集和问题的源代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
double t;       
int sum;       
void Trim(vector<int>& vec,double t) // t为修正参数
{
	int m = vec.size();
	vector<int> temp;
	temp.push_back(vec[0]);
	int i,last = vec[0];
	for(i = 1; i < m ; i++)
		if(vec[i] > last*(1 + t) && (vec[i] <= sum)){
			temp.push_back(vec[i]);
			last = vec[i];
		}
	vec = temp;
}

void MergeList(vector<int>& vec1,int x)
{
	int i,j,k = vec1.size();
	for(i = 0; i < k; i++){
		j = vec1[i] + x;
		vec1.push_back(j);
	}
	sort(vec1.begin(),vec1.end());  // 排序
}


vector<int>& ApproxSubsetSum(vector<int>& Sum,vector<int>& f)
{
	int n = Sum.size();
	vector<int> result;
	result.push_back(0);
	int i,j;
	for(i = 0; i < n; i++){
		MergeList(result,Sum[i]);
		Trim(result,t);
	}
	f = result; 
	return f;
	
}



int main()
{
	vector<int> source;
	int n;       // n为原集合大小，m为指定的子集和
	scanf("%d%d%lf",&n,&sum,&t);
	int i,tmp;
	for(i = 0; i < n; i++){
		scanf("%d",&tmp);
		source.push_back(tmp);
	}
	vector<int> res;
	vector<int> f;
	res = ApproxSubsetSum(source,f);
	for(i = 0; i < res.size(); i++)
		printf("%d ",res[i]);
}