V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
iloveyou
V2EX  ›  问与答

算法苦逼又来求解决方案,一个很简单的问题,大牛们来啊

  •  
  •   iloveyou · 2013-08-03 10:29:08 +08:00 · 3818 次点击
    这是一个创建于 4130 天前的主题,其中的信息可能已经有所发展或是发生改变。
    从a、b、c中随机挑出一个,a出现的几率为20%,b出现的记录为50%,c出现的几率为70%。
    求最简洁效率最高的算法,最好用php。
    第 1 条附言  ·  2013-08-03 11:35:45 +08:00
    把我最终的代码发出来,我遇到的情况更复杂,对象个数未知,对象权重未知。当然原理都是一样的。

    $total_weightiness = 0; //符合条件内容的权重之和
    $weightiness_arr = array(); //存放每个对象权重的范围
    foreach ($final_rules as $key => $value) {
    $weightiness_arr[$key] = $total_weightiness + $value->weightiness;
    $total_weightiness += $value->weightiness;
    }
    $rand = rand(1,$total_weightiness);
    foreach ($weightiness_arr as $key => $value) {
    if($rand < $value)
    return $final_rules[$key];
    }
    第 2 条附言  ·  2013-08-05 08:52:54 +08:00
    又发现一种牛掰的方法:

    $weight = 0;
    $tempdata = array();
    foreach ($data as $one) {
    $weight += $one['weight'];
    for ($i = 0; $i < $one['weight']; $i ++) {
    $tempdata[] = $one;
    }
    }
    $use = rand(0, $weight – 1);
    $one = $tempdata[$use];
    第 3 条附言  ·  2013-08-05 09:08:38 +08:00
    @Mutoo 根据mutoo的方法进一步精简

    $total_weightiness = 0; //符合条件内容的权重之和
    foreach ($final_rules as $key => $value) {
    $total_weightiness += $value->weightiness;
    }
    $rand = rand(1,$total_weightiness);
    foreach ($final_rules as $value) {
    $temp = $rand -= $value->weightiness;
    if($temp < 0)
    return $value;
    }
    19 条回复    1970-01-01 08:00:00 +08:00
    dndx
        1
    dndx  
       2013-08-03 10:30:58 +08:00 via iPad
    70 + 50 + 20 > 100

    这如何实现?
    iloahz
        2
    iloahz  
       2013-08-03 10:32:02 +08:00
    r = rand() % 100;
    if r < 20:
    return a
    else if r < 70:
    return b
    else:
    return c
    wang2191195
        3
    wang2191195  
       2013-08-03 10:36:43 +08:00 via iPhone
    这个要求太高了=_=
    iloveyou
        4
    iloveyou  
    OP
       2013-08-03 10:37:39 +08:00
    @dndx 你可以把百分比理解为权重,就是出现的几率有多大
    iloveyou
        5
    iloveyou  
    OP
       2013-08-03 10:46:07 +08:00
    @iloahz 你这不对,如果a b的权重一样呢
    rwx
        6
    rwx  
       2013-08-03 10:56:24 +08:00
    自己都说是权重了,那就按权重来办啊
    总权重=20+50+70
    取一个 1 到总权重的随机数
    看随机数落到哪个权重范围就选哪个
    iloveyou
        7
    iloveyou  
    OP
       2013-08-03 10:57:18 +08:00
    @rwx 我目前就是这个思路,但是代码很繁琐。求最优解
    binux
        8
    binux  
       2013-08-03 11:01:57 +08:00
    @iloveyou 2L是对的(虽然他没想到你概率加起来不是100%)
    iloveyou
        9
    iloveyou  
    OP
       2013-08-03 11:05:11 +08:00
    @binux 如果有权重一样的呢
    binux
        10
    binux  
       2013-08-03 11:09:40 +08:00
    @iloveyou 你没看到b的条件是a+b吗?
    windywinter
        11
    windywinter  
       2013-08-03 11:11:47 +08:00
    把2L的% 100改成%140就对了。
    iloveyou
        12
    iloveyou  
    OP
       2013-08-03 11:16:16 +08:00
    @binux 恩 sorry,没注意,2楼和6楼思路一样,我也是这样想的,看来只有这种解了。
    binux
        13
    binux  
       2013-08-03 11:18:25 +08:00
    @iloveyou 你自己写过你会注意不到?
    iloveyou
        14
    iloveyou  
    OP
       2013-08-03 11:36:40 +08:00
    @binux 我的情况更复杂,所以代码也和2楼不一样,所以没仔细看
    jjplay
        15
    jjplay  
       2013-08-03 11:48:27 +08:00
    我觉得你是体彩中心新招聘的程序员!!!!!!!!!
    Mutoo
        16
    Mutoo  
       2013-08-03 11:59:58 +08:00
    你需要《代码大全》第12章,表驱动法。

    不需要有百分数表示,用整数就好。
    1) 先求合sum
    2) 产生0~sum之间的随机数
    3) sum依次减去各个权重,直到sum为负数,被减的那个就是被抽中的

    这个算法要求每次减的顺序是一致的,这样才可以保证概率。
    其实就是把古典概型(权数)转化成几何概型(一维长度)
    best1a
        17
    best1a  
       2013-08-03 18:14:42 +08:00
    @Mutoo +1,遗传算法中貌似把这叫做轮盘赌选择法
    justfindu
        19
    justfindu  
       2013-08-05 09:03:09 +08:00
    http://www.helloweba.com/view-blog-216.html

    类似于这种?

    表示不会贴代码~

    只是这个示例里面有一个转盘范围 min和max , v表示权重或者叫做概率~ 然后就可以抽奖了~
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2957 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 03:42 · PVG 11:42 · LAX 19:42 · JFK 22:42
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.