| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 876 人关注过本帖
标题:求全部可能的算法
只看楼主 加入收藏
qunxingw
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:贵宾
威 望:24
帖 子:1676
专家分:7295
注 册:2011-6-30
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:9 
求全部可能的算法
有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
obstratiker
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:1
帖 子:198
专家分:758
注 册:2011-5-5
收藏
得分:10 
你的太长了所以没看,我自己写了个,输入全是整数,并且限定输入是9个数
可以打印出你要求的

#include <stdio.h>
#define N 10

int main(void)
{
    int    a[9]=,b[36]=;
    int i,j,x=0,p,q,min;
    printf("input 9 numbers:\n");
    scanf("%d%d%d%d%d%d%d%d%d",&a[0],&a[1],&a[2],&a[3],&a[4],&a[5],&a[6],&a[7],&a[8]);
    printf("\n");
    min=a[0]+a[1]-N;
    for(i=0;i<8;i++)
        for(j=i+1;j<9;j++)
        {
            b[x]=a[i]+a[j];
            if(b[x]==N)
                printf("%d + %d = %d\n",a[i],a[j],b[x]);
            if(b[x]-N<min&&b[x]-N!=0)
            {
                p=i;
                q=j;
            }
            x++;
        }
    printf("most close to N:\n");
    printf("%d + %d = %d\n",a[p],a[q],a[p]+a[q]);
    return 0;
}
2012-07-22 22:19
obstratiker
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:1
帖 子:198
专家分:758
注 册:2011-5-5
收藏
得分:0 
哦,声明时a[9]和b[36]的等号没有去掉,你要调试的话得去掉它们
2012-07-22 22:21
obstratiker
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:1
帖 子:198
专家分:758
注 册:2011-5-5
收藏
得分:0 
晕,自己发现了bug,主要是能打印出多个等于N的,而不能打印多个最接近N的,修改了一下,现在可以了


#include <stdio.h>
#include <math.h>
#define N 10

int main(void)
{
    int    a[9],b[36];
    int i=0,j=1,x=0,min;
    printf("input 9 numbers:\n");
    scanf("%d%d%d%d%d%d%d%d%d",&a[0],&a[1],&a[2],&a[3],&a[4],&a[5],&a[6],&a[7],&a[8]);
    printf("\nN = %d\n\n",N);
    while(a[i]+a[j]-N==0)
    {
        j++;
        if(j==9)
        {
            i++;
            j=0;
        }
    }
    min=abs(a[i]+a[j]-N);
    for(i=0;i<8;i++)
        for(j=i+1;j<9;j++)
        {
            b[x]=a[i]+a[j];
            if(b[x]==N)
                printf("%d + %d = %d\n",a[i],a[j],b[x]);
            if(abs(b[x]-N)<min&&(b[x]-N)!=0)
                min=abs(b[x]-N);
            x++;
        }
    printf("most close to N:\n");
    for(i=0;i<8;i++)
        for(j=i+1;j<9;j++)
        {
            if(abs(a[i]+a[j]-N)==min)
                printf("%d + %d = %d\n",a[i],a[j],a[i]+a[j]);
        }
    return 0;
}
2012-07-22 22:42
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
netlin
Rank: 13Rank: 13Rank: 13Rank: 13
等 级:贵宾
威 望:24
帖 子:544
专家分:4308
注 册:2012-4-9
收藏
得分:10 
分析题目:
求全部可能的算法
有9个数,可任取其中几个数(这里应该指1~9个数),使之和与另一已知N数最接近(这点很重要)。我编的程序能够找出这几个数,但不全,主要问题如例所示:如9个数为了 5 5 3 7 2 8 555 5555 5555.5  找出和为10的数,按理应该找到  5+ 5    3+7 2+8  这几个情况,但我的结果只能找到2+8的情况。主要是我在扫描循环时只保存了最后的最小值。

做自己喜欢的事!
2012-07-23 20:21
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
obstratiker
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:1
帖 子:198
专家分:758
注 册:2011-5-5
收藏
得分:0 
以下是引用qunxingw在2012-7-23 21:00:19的发言:

你用b[x]有效的处理了相同个数的数,相加后相同的最接近数,我要的问题应该已经可以很好的可以处理了,谢谢你哟。不好意思请你帮我理解下,你的这个循环意思。while(a+a[j]-N==0)
    {
        j++;
        if(j==9)
        {
            i++;
            j=0;
        }
    }
哦,这个主要是为了产生一个 a[i]+a[j]-N 的值且这个值不等于 0 ,把它赋值 min ,然后遍历 a[i] 来看 a[i]+[j] 是否有更接近 N 的。
不过这样你看又有 bug ,必须加一个条件 if(i==8){break;} 来防止数组中所有的值两两相加都等于 N 的情况。
至于允许好几个数相加的方法,我想了一下,恐怕不是现在力所能及的了…
2012-07-23 22:13
qunxingw
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:贵宾
威 望:24
帖 子:1676
专家分:7295
注 册:2011-6-30
收藏
得分:0 
其实不用考虑分==0,!=0的情况,通过比较只要是比上个数小的就保存,有==0的当然是最接近的数,没有就是相比较最小的,其他不同个数相加找最小的方法一样,只是打印时要考虑好多情况,这个已经解决。

www.qunxingw.wang
2012-07-23 22:30
obstratiker
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:1
帖 子:198
专家分:758
注 册:2011-5-5
收藏
得分:0 
回复 9楼 qunxingw
哦哦,对的~确实不用考虑等于零的情况了
2012-07-23 22:45
快速回复:求全部可能的算法
数据加载中...
 
   



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

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