这道笔试题，我是从chinaunix论坛上看到的，原帖网址为：bbs.chinaunix.net/thread-3604016-1-1.html，是网友snowboy9859发的。原帖是：“有N个正实数（注意是实数，大小升序排列）x1，x2，……，xN，另有一个实数M。需要选出若干个x，使这几个x的和与M最接近。请描述实现算法，并指出算法复杂度。”
看到问题之后的刹那间，脑海里浮想联翩，混混沌沌，思路很不清晰。现在回想一下，当时自己脑子里是在设想符合题目要求的各种情况。也就是说，我的潜意识的第一反应是用穷举法解这道题，可是要考虑的情况似乎太多了，所以思路就乱了。
然后，我开始认真察看网友的回复，果然，在很靠前的位置，就有网友提出用穷举法，但他说得很概括。回复楼主的网友很多，绝大多数都提出了自己的想法，其中很多人提到这道题类似“0/1背包问题”，可以借助解“0/1背包问题”的算法解这道题。所以我又到其他网站上搜索关于“0/1背包问题”的知识，搜到了很多，其中很多大侠都给出了自己的源代码。博客园上的一位大侠张玉彬（www.cnblogs.com/jillzhang/archive/2007/10/06/915035.html#2242617）在讲解“0/1背包问题”之前，先提到了穷举法：“这种问题最简单的方法就是找出这个向量的所有子集，如同找出幂集中的子集一样，但这种遍历的方法恐怕并不会被聪明的我们所使用”。“幂集”一词，本来是数学上的，对我来说很少听到，可它一下子让我想起了《数据结构》上有一道题是解一个集合的幂集的（怪不得老师向他的每一个学生都推荐这本书（C语言版，严蔚敏、吴伟民编著，清华大学出版社）~~）。
看完了张玉彬的那篇文章（其实，在此之前，我已经看了几篇其他网站上的相关文章），我学到了两种方法解那道搜狐笔试题，一个是穷举法，另一个是解“0/1背包问题”的方法（当然，用穷举法也能解“0/1背包问题”，但关于“0/1背包问题”有更经典的独特方法）。现在，我要用穷举法来解这道题，因为现在我只实现了穷举法。关于“0/1背包问题”的更好的解法，我还得再回味一下，我觉得自己理解的还不够深入。
穷举法，也就是数学上求集合幂集的方法，用试探和回溯的搜索技术求解。关于幂集和回溯法，上文提到的书中第6.7讲得挺好的。
穷举法要列举2^N种情况，希望大家伙儿多多提出自己的想法，找出更高效的算法。穷举法程序源代码如下：“
using std::cout;
using std::endl;
using std::cin;
#include <vector> // list class-template definition
using std::vector;
#include <algorithm>
using std::for_each;
#include <numeric> // accumulate is defined here
using std::accumulate;
vector<float> nearB;
float M = 0;
float nearest = 0;
bool theFirstB = true;
void GetNearestPowerSet(int i, vector<float> &A, vector<float> &B) {
// 线性表A表示集合A, 线性表B表示幂集Rou(A)的一个元素.
// 第一次调用本函数时, B为空表, i=1.
if (i > A.size())
{
// 当前B即为Rou(A)的一个元素, 为了完成目标, 要进行以下操作:
// 1. 求出B中所有元素的和sumB;
// 2. 求出sumB-M的差值的绝对值e;
// 3. if e<nearest then (nearest=e; and 将B暂存);
// 注: 变量nearest中存放的是所有所求得的sumB与M差值的绝对值的最小值
float sumB = accumulate(B.begin(), B.end(), 0);
float e = abs(sumB-M);
if (theFirstB)
{
theFirstB = false;
nearest = e;
nearB = B;
}
else
{
if (e < nearest)
{
nearest = e;
nearB = B;
}
}
}
else
{
float x = A.at(i-1);
B.push_back(x); // 取第i个元素, 注vector元素下标从0算起:
GetNearestPowerSet(i+1, A, B);
B.pop_back(); // 舍第i个元素
GetNearestPowerSet(i+1, A, B);
}
}
void OutputElements(float elements)
{
cout << elements << ' ';
}
void PrintResult(float value, vector<float> &theVector)
{
cout << "the nearest different value with " << M << " is: " << value << '\n';
cout << "the elements is: ";
for_each(theVector.begin(), theVector.end(), OutputElements);
cout << endl;
}
int main()
{
int N = 0;
vector<float> A;
vector<float> B;
float element = 0;
cout << "请输入目标值(float型): ";
cin >> M;
cout << "请输入float型元素(输入0结束): ";
while (cin>>element, element)
{
A.push_back(element);
}
GetNearestPowerSet(1, A, B);
PrintResult(nearest, nearB);
return 0;
}
”。