| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 876 人关注过本帖
标题:求全部可能的算法
取消只看楼主 加入收藏
qunxingw
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:贵宾
威 望:24
帖 子:1676
专家分:7295
注 册:2011-6-30
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:3 
求全部可能的算法
有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;

}
搜索更多相关主题的帖子: include 
2012-07-22 20:19
qunxingw
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:贵宾
威 望:24
帖 子:1676
专家分:7295
注 册:2011-6-30
收藏
得分:0 
谢谢你的回复,不过这里有几个问题需要讨论,第一,这个最接近数是未知的,不是说一定是10,随着需要而定,第二,从这9个数中找满足N的最小值时,不一定只选二个数相加,主要是遍历所有可能,只要是最小的就行,可以选择1个数,2个数,....或所有数。
这个想法来源于工作,有若干块金条,从中可任选几条,使之和重,与另一客户要求的重量最接近。

www.qunxingw.wang
2012-07-23 20:12
qunxingw
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:贵宾
威 望:24
帖 子:1676
专家分:7295
注 册:2011-6-30
收藏
得分:0 
你用b[x]有效的处理了相同个数的数,相加后相同的最接近数,我要的问题应该已经可以很好的可以处理了,谢谢你哟。不好意思请你帮我理解下,你的这个循环意思。while(a[i]+a[j]-N==0)
    {
        j++;
        if(j==9)
        {
            i++;
            j=0;
        }
    }

www.qunxingw.wang
2012-07-23 21:00
qunxingw
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:贵宾
威 望:24
帖 子:1676
专家分:7295
注 册:2011-6-30
收藏
得分:0 
其实不用考虑分==0,!=0的情况,通过比较只要是比上个数小的就保存,有==0的当然是最接近的数,没有就是相比较最小的,其他不同个数相加找最小的方法一样,只是打印时要考虑好多情况,这个已经解决。

www.qunxingw.wang
2012-07-23 22:30
快速回复:求全部可能的算法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.018204 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved