求解：用穷举法解决子集和（subset sum problem）的有关问题

求解：用穷举法解决子集和（subset sum problem）的问题
就是已知一个正整数集S={2,3,5,7…}，给定一个正整数N，求S的一个子集p，使的p的所有元素相加结果最接近N
贪心算法实现了，
不过现在想用"穷举"的方法解一下题懂思路不过编程能力差不知道怎么用穷举实现
求解！！

------解决方案--------------------
穷举，就是遍历所有S的子集，
用01表示元素是否存在于子集中

从0——2^S基数的二进制数循环
00000……000
00000……001
00000……010
……
111111111111

对应的位置表示S第X元素是否存在与子集p，，，穷举完成，记录差距最小的即可
------解决方案--------------------
写了个递归版本，测试几个数据好像都是对的，楼主参考下：

C/C++ code

int getMinDifference(int s[], int start, int end, int n){
    if(start==end || n<=0) return n>0?n:-n;

    int index = 0;
    for(index=start; index<end&&s[index]<=n; ++index);

    if(index == start){
        return n>s[index]-n?s[index]-n:n;
    }

    int picked = getMinDifference(s,start, index-1, n-s[index-1]);
    int unpicked = getMinDifference(s,start,index-1,n);

    return picked < unpicked?picked:unpicked;
}

int main()
{
    int s[] = {2,3,7,8,9};
    int n = 5;
    int r = getMinDifference(s,0,5,n);
    printf("result: %d\n",r);

    return 0;
}

------解决方案--------------------
穷举要么就是很多层for循环，每层循环有0和1,0代表不取，1代表取。或者用位运算，两层for循环即可。
如下：
  for(int  x   =   1;   x < (1 << Size); ++x)  
	   {  
		  for(int y = 0; y < Size; ++y)  
		 {  
			  if(x & (1 << y))
			  {
			 	  cout << a[y];
			  }
		 }  
		 cout  <<  endl;  
	   }

求解：用穷举法解决子集和（subset sum problem）的有关问题

相关推荐