C趣味程序百例(24)小明买书

76.小明买书
假期小明和爸爸去了书店。他选了六本书，每本书的单价分别是:3.1、1.7、2、5.3、0.9、7.2。可惜小明爸爸只带了十几块钱。为了让小明过一个愉快的假期，他的父亲扔进去同意买书，但是提出了邮购的要求，要求小明从6本书中挑选若干本，使单价之和最接近10。你能帮小明解决这个问题吗？
*问题分析与算法设计
分析问题的含义，可以将问题简化为:从6个数中选择一个数的和，使和与10的差最小。
题目隐含了两个问题。一个是如何从六个数字中选择一个数字；二是求与10的差。
从六个数字中选一个数字，其实就是从六个数字中选一个数字进行组合。每个数在组合过程中只有两种情况:要么选择参与求和，要么不选择不参与求和。这样，无论每个数是否参与求和，都可以用六个循环来组合所有可能的情况。
关于求与10的差要注意:差的意义是指差的绝对值。比如:“9-10=-1”和“11-10=1”，但是9和11和10的差是1。认为“9”和“10”的差是-1是错误的。
*程序和程序注释
# include
# include
void main()
{
int d[6]，m，I，j；
龙b[63]，旗；
float c[6]，min，x；
printf("请输入6本书的价格:")；
for(I = 0；i for(i=0，min=-1，d[0]= 0；d[0]for(d[1]= 0；d[1]for(d[2]= 0；d[2]for(d*思考题
可见程序中六个数求所有组合的算法并不好，使用六个循环进行处理使得程序不够简洁。可以设计更通用和优化的算法来产生所有组合。= 0；d[3]for(d[4]= 0；d[4]for(d[5]= 0；d[5] {
for(flag=0，x=0，j = 5；j > = 0；J-)
/* flag:六个数的组合用对应的十进制位X表示:六个数组合对应的sum */
{
X+= c[j]* d[j]；flag = flag * 10+d[j]；
}
x=((x-10>0)？x-10:10-x)；/*x:总和与10的差*/
if(min {
min = x；/*处理第一个计算的差值min */
b[i++]= flag；/*b[]:数组I:具有相同min标志的b[]数组的下标*/
}
else if(min-x > 1 . e-6)/*处理新的min */
{
min = b[0]= flag；I = 1；
}
else if(fabs((double)x-min)b[i++]= flag；/*处理相等的min */
}
for(m = 0；m {
printf("10(+ -)%.2f= "，min)；
for(flag=b[m]，j = 0；标志> 0；++，flag/= 10)
if (flag% 10)/*将b[]中存储的标志还原为数字的组合*/
if(flag > 1)printf(" % . 2f+"，c[j])；
else printf("%.2f\n "，c[j])；
}
}
*运行结果
请输入6本书的价格:3.1 1.7 2.0 5.3 0.9 7.2
10(+-)0.10 = 2.00+0.90+7.20。0.10 = 1.70+2.00+5.30+0.90
10(+-)0.10 = 3.10+1.70+5.30

[3]