求全部可能的算法
有9个数,可任取其中几个数,使之和与另一已知N数最接近。我编的程序能够找出这几个数,但不全,主要问题如例所示:如9个数为了 5 5 3 7 2 8 555 5555 5555.5 找出和为10的数,按理应该找到 5+ 5 3+7 2+8 这几个情况,但我的结果只能找到2+8的情况。主要是我在扫描循环时只保存了最后的最小值。我实在找不出一个好方案把相同个数都是最小值的保存下来,求指导。源码如下:#include<iostream>
#include<math.h>
#include <cstdlib>
//#define N 253 //要求从数组A[]中找若干数之和与此N最接近的数
using namespace std;
int i,j,k,l,i1,k1,i2,j2,k2,i3,j3,k3,i1_1,i2_2,i3_3,j1_1,j2_2,k3_3,k2_2,j3_3,i4,
j4,k4,l4,i4_4,j4_4,k4_4,l4_4;
double n, sum=0,min0=0.1,min1=0.1,min2=0.1,min_other1=0.1,min_other2=0.1,
min3=0.1,min_other3=0.1,min4=0.1,min_other4=0.1,min=50000, min_other=50000;
double a[9];//={110.80,256.8,587.5,111.3,554.9,1495.5,1204.7,1200.3,853.6};
int main()
{
cout<<"此程序大意是从(from)一个含9块金条的数组中任取几条,使其重量之(SUM)和与另要求的金重数N最接近,并找出这些数。"<<endl;
cout<<"请现在输入N的重量数N=(不要单位):"<<endl;
cin>>n; // 要求从数组A[]中找若干数之和与此N最接近的数
cout<<endl;
cout<<"请现在请输入(please input)9 块金条(weight)重量数!(提示:每输入一个重量按一下(press < enter > 回车键)"<<endl;
for( i=0; i<=8; i++)
cin>>a[i];
for( i=0; i<=8; i++)
{
sum+=a[i];
}
if(min>=fabs(sum-n))
{ min=fabs(sum-n);
min0=min;
}
for(i=0;i<=8;i++) //取1个数或8个数找最小值,并保存数组位置
{
//cout<<"a["<<i<<"]="<<a[i]<<endl;
if(min>=fabs(a[i]-n))
{
min=fabs(a[i]-n);
i1=i;
min1=min;
}
if(min_other>=fabs(sum-a[i]-n))
{
min_other=fabs(sum-a[i]-n);
i1_1=i;
min_other1=min_other;
}
}
for(i=0; i<=8; i++) //取2个数或7个数找最小值,并保存数组位置
for(j=0; j<i; j++)
{
// cout<<"a["<<i<<"]+"<<"a["<<j<<"]="<<a[i]+a[j]<<endl;
if(min>=fabs(a[i]+a[j]-n))
{
min=fabs(a[i]+a[j]-n);
i2=i;
j2=j;
min2=min;
}
if(min_other>=fabs(sum-(a[i]+a[j])-n))
{
min_other=fabs(sum-(a[i]+a[j])-n);
i2_2=i;
j2_2=j;
min_other2=min_other;
}
}
for( i=0; i<=8; i++) //取3个数或6个数找最小值,并保存数组位置
for( j=0; j<i; j++)
for( k=0; k<j; k++)
{
//cout<<"a["<<i<<"]+"<<"a["<<j<<"]+"<<"a["<<k<<"]="<<a[i]+a[j]+a[k]<<endl;
if(min>=fabs(a[i]+a[j]+a[k]-n))
{
min=fabs(a[i]+a[j]+a[k]-n);
i3=i;
j3=j;
k3=k;
min3=min;
}
if(min_other>=fabs(sum-(a[i]+a[j]+a[k])-n))
{
min_other=fabs(sum-(a[i]+a[j]+a[k])-n);
i3_3=i;
j3_3=j;
k3_3=k;
min_other3=min_other;
}
}
for( i=0; i<=8; i++) //取4个数或5个数找最小值,并保存数组位置
for( j=0; j<i; j++)
for( k=0; k<j; k++)
for( l=0; l<k; l++)
{
// cout<<"a["<<i<<"]+"<<"a["<<j<<"]+"<<"a["<<k<<"]+"<<"a["<<l<<"]="<<a[i]+a[j]+a[k]+a[l]<<endl;
if(min>=fabs(a[i]+a[j]+a[k]+a[l]-n))
{
min=fabs(a[i]+a[j]+a[k]+a[l]-n);
i4=i;
j4=j;
k4=k;
l4=l;
min4=min;
}
if(min_other>=fabs(sum-(a[i]+a[j]+a[k]+a[l])-n))
{
min_other=fabs(sum-(a[i]+a[j]+a[k]+a[l])-n);
i4_4=i;
j4_4=j;
k4_4=k;
l4_4=l;
min_other4=min_other;
}
}
cout<<"原数组为:"<<endl;
for( i=0; i<=8;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"总和sum="<<sum<<endl;
cout<<"请找要求与N最接近的数N="<<n<<endl;
if(min<min_other) // 输出找到要求数的结果,正才有最小
{
if(min==min0)
{
cout<<"min0="<<min0<<endl;
cout<<"很高兴找到全数总和就是最接近数:"<<sum<<endl;
}
if(min==min1)
{
cout<<"min1="<<min1<<endl;
cout<<"[a"<<i1<<"]="<<a[i1]<<endl;
cout<<"很高兴找到此数为:"<<a[i1]<<endl;
}
if(min==min2)
{
cout<<"min2="<<min2<<endl;
cout<<"a["<<i2<<"]+"<<"a["<<j2<<"]="<<a[i2]+a[j2]<<endl;
cout<<"很高兴找到此数为:"<<a[i2]<<"; "<<a[j2]<<endl;
}
if(min==min3)
{
cout<<"min3="<<min3<<endl;
cout<<"a["<<i3<<"]+"<<"a["<<j3<<"]+a["<<k3<<"]="<<a[i3]+a[j3]+a[k3]<<endl;
cout<<"很高兴找到此数为:"<<a[i3]<<"; "<<a[j3]<<"; "<<a[k3]<<endl;
}
if(min==min4)
{
cout<<"min4="<<min4<<endl;
cout<<"a["<<i4<<"]+"<<"a["<<j4<<"]+"<<"a["<<k4<<"]+"<<"a["<<l4<<"]="<<a[i4]+a[j4]+a[k4]+a[l4]<<endl;
cout<<"很高兴找到此数为:"<<a[i4]<<"; "<<a[j4]<<"; "<<a[k4]<<"; "<<a[l4]<<endl;
}
}
else if(min==min_other) //正反都有最小值
{
if(min==min0)
{
cout<<"min0="<<min0<<endl;
cout<<"很高兴找到全数总和就是最接近数:"<<sum<<endl;
}
if(min==min1)
{
cout<<"min1="<<min1<<endl;
cout<<"[a"<<i1<<"]="<<a[i1]<<endl;
cout<<"很高兴找到此数为:"<<a[i1]<<endl;
}
if(min==min2)
{
cout<<"min2="<<min2<<endl;
cout<<"a["<<i2<<"]+"<<"a["<<j2<<"]="<<a[i2]+a[j2]<<endl;
cout<<"很高兴找到此数为:"<<a[i2]<<"; "<<a[j2]<<endl;
}
if(min==min3)
{
cout<<"min3="<<min3<<endl;
cout<<"a["<<i3<<"]+"<<"a["<<j3<<"]+a["<<k3<<"]="<<a[i3]+a[j3]+a[k3]<<endl;
cout<<"很高兴找到此数为:"<<a[i3]<<"; "<<a[j3]<<"; "<<a[k3]<<endl;
}
if(min==min4)
{
cout<<"min4="<<min4<<endl;
cout<<"a["<<i4<<"]+"<<"a["<<j4<<"]+"<<"a["<<k4<<"]+"<<"a["<<l4<<"]="<<a[i4]+a[j4]+a[k4]+a[l4]<<endl;
cout<<"很高兴找到此数为:"<<a[i4]<<"; "<<a[j4]<<"; "<<a[k4]<<"; "<<a[l4]<<endl;
}
if(min_other==min_other1)
{
cout<<"min_other1="<<min_other1<<endl;
cout<<"和值为"<<sum-a[i1_1]<<endl;
cout<<"很高兴找到不含这个数的其他数(except): "<<a[i1_1]<<endl;
}
if(min_other==min_other2)
{
cout<<"min_other2="<<min_other2<<endl;
cout<<"和值为"<<sum-a[i2_2]-a[j2_2]<<endl;
cout<<"很高兴找到不含这几个数的其他数(except): "<<a[i2_2]<<"; "<<a[j2_2]<<endl;
}
if(min_other==min_other3)
{
cout<<"min_other3="<<min_other3<<endl;
cout<<"和值为"<<sum-a[i3_3]-a[j3_3]-a[k3_3]<<endl;
cout<<"很高兴找到不含这几个数的其他数(except): "<<a[i3_3]<<"; "<<a[j3_3]<<"; "<<a[k3_3]<<endl;
}
if(min_other==min_other4)
{
cout<<"min_other4="<<min_other4<<endl;
cout<<"和值为"<<sum-a[i4_4]-a[j4_4]-a[k4_4]-a[l4_4]<<endl;
cout<<"很高兴找到不含这几个数的其他数(except): "<<a[i4_4]<<"; "<<a[j4_4]<<"; "<<a[k4_4]<<"; "<<a[l4_4]<<endl;
}
}
else //仅反才有最小值。
{
if(min_other==min_other1)
{
cout<<"min_other1="<<min_other1<<endl;
cout<<"和值为"<<sum-a[i1_1]<<endl;
cout<<"很高兴找到不含这个数的其他数(except): "<<a[i1_1]<<endl;
}
if(min_other==min_other2)
{
cout<<"min_other2="<<min_other2<<endl;
cout<<"和值为"<<sum-a[i2_2]-a[j2_2]<<endl;
cout<<"很高兴找到不含这几个数的其他数(except): "<<a[i2_2]<<"; "<<a[j2_2]<<endl;
}
if(min_other==min_other3)
{
cout<<"min_other3="<<min_other3<<endl;
cout<<"和值为"<<sum-a[i3_3]-a[j3_3]-a[k3_3]<<endl;
cout<<"很高兴找到不含这几个数的其他数(except): "<<a[i3_3]<<"; "<<a[j3_3]<<"; "<<a[k3_3]<<endl;
}
if(min_other==min_other4)
{
cout<<"min_other4="<<min_other4<<endl;
cout<<"和值为"<<sum-a[i4_4]-a[j4_4]-a[k4_4]-a[l4_4]<<endl;
cout<<"很高兴找到不含这几个数的其他数(except): "<<a[i4_4]<<"; "<<a[j4_4]<<"; "<<a[k4_4]<<"; "<<a[l4_4]<<endl;
}
}
system("pause");
return 0;
}