| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
ADSL如何秒变专线,公网IP盒子了解一下千里之行 始于足下
共有 303 人关注过本帖
标题:请高手帮忙解决 组合称算法问题,万分感谢!要求如下
只看楼主 加入收藏
PhD_Lee
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2019-4-19
结帖率:0
  已结贴   问题点数:20  回复次数:3   
请高手帮忙解决 组合称算法问题,万分感谢!要求如下
有10个数a1,a2,a3....a10,数据格式为浮点数,任意个数组合求和(1个数值,2个数和,3个数和,4个数和....10个数和,求和时10个数不重复使用,总共1023种组合结果),其和值与数据b(浮点数)进行比较,输出最接近b值的数组,(如a1+a2+a3最接近b,则输出a1,a2,a3);如果同时有多个值出现,则优先输出组合个数少,单个组合数排位靠前的数组(如a1+a2=a3=a4+a5+a6最接近b,结果输出为a3;  a1=a2=a5=a9最接近b,结果输出为a1;  a1+a2=a1+a4最接近b,结果输出为a1,a2;  a3+a7=a4+a5最接近b,结果输出为a3,a7  ).
 
求大神帮忙研究下代码如何写!!!万分感谢。。
搜索更多相关主题的帖子: 组合 要求 个数 结果 输出 
2019-04-19 14:50
word123
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:13
帖 子:333
专家分:1622
注 册:2014-4-5
  得分:10 
看下能不能用递归来做,对每一个数取还是不取,共有2^10=1024种结果,除去所有数都不取的情况,共有1023种可能
Sum=0,i=0
F(array , stack , i , sum)
  //取第i个数,将第i个数存到stack
  //若sum+ai更接近目标,则存储当前stack中的所有数,该序列当前最优
  //若和当前最优相同,则选择长度最小的(若长度一样则不更新,因为下标是从最小的开始加入的)
  F(array , stack , i+1 , sum+ai)
  //当i后面的所有数都遍历完,从栈中弹出当前值ai
  Stack.pop()

  F(array , stack , i+1 , sum)   //不取第i个数
2019-04-19 16:40
PhD_Lee
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2019-4-19
  得分:0 
完整代码能写一下吗?高手兄
2019-04-20 09:07
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:313
帖 子:6509
专家分:37778
注 册:2011-1-18
  得分:10 
第一种方法:用任意一种方法遍历,遇到比之前更接近的则……,一样接近的则根据题目规则判断是否替换。
double min_delta = DBL_MAX;
unsigned min_count = 0;
unsigned min_mask = 0;
for( unsigned mask=1; mask!=1024; ++mask )
{
    sum = mask对应bit为1的需要参与求和,假如 mask 是二进制的 1101,那么 a[0]*1 +a[1]*0 + a[2]*1 + a[3]*1 + ……
    if( sum和b的差比min_delta更小 或 与min_delta一样大但…… )
    {
        ……
    }
}

第二种方法:直接按照题目规则遍历,遇到比之前更接近的则……。一样接近的就可以直接舍弃。
double min_delta = DBL_MAX;
for( unsigned mask=1; mask!=-1; mask=next(maks) )
{
    sum = mask对应bit为1的需要参与求和,假如 mask 是二进制的 1101,那么 a[0]*1 +a[1]*0 + a[2]*1 + a[3]*1 + ……
    if( sum和b的差比min_delta更小 )
    {
        ……
    }
}
next函数就比较复杂了
unsigned next( unsigned bits )
{
    int leftzero = 10-1;
    for( ; leftzero>=0 && (bits&(1u<<leftzero))!=0; --leftzero );
    if( leftzero == -1 )
        return leftzero;

    int afterone = leftzero-1;
    for( ; afterone>=0 && (bits&(1u<<afterone))==0; --afterone );
    if( afterone == -1 )
        return (bits>>leftzero)|1u;

    return ((((0-1u)<<(leftzero+1))&bits)>>(leftzero-afterone-1))|(1u<<(afterone+1))|(((1u<<afterone)-1)&bits);
}
2019-04-22 09:32







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

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