数学回味系列之23 - 小明买书

问题提出：

       小明假期同爸爸一起去书店，他选中了六本书，每本书的单价分别为：3.1，1.7，2，5.3，0.9和7.2。不巧的是，小明的爸爸只带了十几块钱，为了让小明过一个愉快的假期，爸爸扔然同意买书，但提邮购一个要求，要小明从六本书中选出若干本，使得单价相加所得的和同10最接近。

解题思路：

       可以将题目简化为：从6个数中选取若干个求和，使得和与10的差值最小。

       这里面隐含两个问题，一是如何选择若干数，二是求差值。

       参考代码：

#include <math.h>
#include <iostream>
using namespace std;

int main()
{
	double dpBooks[6] = {3.1, 1.7, 2.0, 5.3, 0.9, 7.2}; 
	const double dLimit = 10;
	double dMinAbs = 100; //给个比较大的数。
	long nIndex = 0;
	for (long k=0; k<64; k++)
	{
		double dSum=0;
		long nBitMask=1;
		for (long n=0; n<6; n++)
		{
			if (k & nBitMask)
				dSum += dpBooks[n];
			nBitMask = nBitMask<<1;
		}
		double dAbs = fabs(dSum - dLimit);
		if (dAbs < dMinAbs)
		{
			dMinAbs = dAbs;
			nIndex = k;
		}
	}
	// nIndex 是最佳结果，下面打印
	long nBitMask=1;
	double dSum=0;
	for (long n=0; n<6; n++)
	{
		if (nIndex & nBitMask)
		{
			cout<< dpBooks[n]<<" ";
			dSum += dpBooks[n];
		}
		nBitMask = nBitMask<<1;
	}
	cout<<endl;
	cout<<"Sum="<<dSum<<endl;

	getchar();
	return 0;
}