不同中奖概率的多奖包抽奖几种算法

需求描述：总共有很多个奖包，每个奖包的中奖概率是人为自由设定的，规定每次抽奖必须抽中。
算法分类：
一、最初自行编写的算法：

<?php
//目标id：随机抽中的奖包id
$pid = 0;
//$pList为奖包信息存放数组，是从数据库中提取出来的
//为方便研究，这里直接给$pList赋值
$pList = array
(
    [0] => array
        (
            ["id"] => 65,
            ["percent"] => 10
        ),
    [1] => array
        (
            ["id"] => 64,
            ["percent"] => 50
        ),
    [2] => array
        (
            ["id"] => 63,
            ["percent"] => 20
        ),
    [3] => array
        (
            ["id"] => 62,
            ["percent"] => 80
        ),
    [4] => array
        (
            ["id"] => 61,
            ["percent"] => 30
        )
);
//中奖概率之总和
$sum = 0;
//以中奖概率总和为上限，以1为起始键名（1为自增值），以表的id为键值的数组
//ps：本想直接给$randomArr赋值，上面的代码也省略，但这样不利于理解和对比
$randomArr = array();
if(!empty($pList)){
    foreach($pList as $key=>$value){
        $newSum = $sum + $value["percent"];
        for($i=$sum+1;$i<=$newSum;$i++){
            //给$randomArr赋值，中奖概率为键名，id为键值
            $randomArr[$i] = $value["id"];
        }
        $sum = $newSum;
    }
}
//随机出的数，作为抽中的$randomArr数组的键名
$random = 0;
if($sum > 0){
    $random = mt_rand(1,$sum);
}
//确定随机抽中的奖包id
if($random > 0){
    $pid = $randomArr[$random];
}

思路：用中奖概率为键名，奖包id为键值组建数组 => 随机键名（中奖概率） => 根据键名确定键值（奖包id）
总结：优点是利于理解，缺点是效率不高

二、经领导指点改进后的算法：

<?php
//目标id：随机抽中的奖包id
$pid = 0;
//$pList为奖包信息存放数组，是从数据库中提取出来的
//为方便研究，这里直接给$pList赋值
$pList = array
(
    [0] => array
        (
            ["id"] => 65,
            ["percent"] => 10
        ),
    [1] => array
        (
            ["id"] => 64,
            ["percent"] => 50
        ),
    [2] => array
        (
            ["id"] => 63,
            ["percent"] => 20
        ),
    [3] => array
        (
            ["id"] => 62,
            ["percent"] => 80
        ),
    [4] => array
        (
            ["id"] => 61,
            ["percent"] => 30
        )
);
//中奖概率之总和
$sum = 0;
//中奖概率存放数组，以id为键名，以中奖概率的累加和为键值
//赋值后的$randomArr，形如$randomArr = array(0=>0,65=>10,64=>50,...,61=>30);
$randomArr = array();
//为了方便下面随机数范围的比较而设定
$randomArr[0] = 0;
if(!empty($pList)){
    foreach($pList as $key=>$value){
        $sum = $sum + $value["percent"];
        $randomArr[$value["id"]] = $sum;
    }
}
//随机出的概率数
$random = 0;
if($sum > 0){
    $random = mt_rand(1,$sum);
}
//每次循环参加比较的上一个key的值
$oldKey = 0;
foreach($randomArr as $key=>$value){
    if($key > 0){
        //根据随机数大小范围比较，确定随机出的奖包id
        if($random>$randomArr[$oldKey] && $random<=$randomArr[$key]){
            $pid = $key;
        }
    }
    $oldKey = $key;
}

思路：用奖包id为键名，中奖概率累加和为键值组建数组 => 随机键值（中奖概率） => 判断中奖概率的范围 => 根据范围确定键名（奖包id）
总结：优点是易于理解，且执行效率高，只是前期算法设计时需多动脑筋

三、网络搜来的经典算法：

<?php
//目标id：随机抽中的奖包id
$pid = 0;
//$pList为奖包信息存放数组，是从数据库中提取出来的
//为方便研究，这里直接给$pList赋值
$pList = array
(
    [0] => array
        (
            ["id"] => 65,
            ["percent"] => 10
        ),
    [1] => array
        (
            ["id"] => 64,
            ["percent"] => 50
        ),
    [2] => array
        (
            ["id"] => 63,
            ["percent"] => 20
        ),
    [3] => array
        (
            ["id"] => 62,
            ["percent"] => 80
        ),
    [4] => array
        (
            ["id"] => 61,
            ["percent"] => 30
        )
);
//中奖概率之总和
$sum = 0;
if(!empty($pList)){
    //求$sum的值
    foreach($pList as $key=>$value){
        $sum = $sum + $value["percent"];
    }
    //根据数学概率论的“黑箱摸球”原理设计、取得抽中的奖包id
    if($sum > 0){
        foreach($pList as $key=>$value){
            //以剩余循环概率和为基数，生成随机数
            $random = mt_rand(1,$sum);
            //若生成的随机数在本次循环的中奖概率范围内，则抽中本奖包，循环终止
            if($random <= $value["percent"]){
                $pid = $value["id"];
                break;
            }else{
                //若循环未终止，则每循环一次，$sum需要减去本次循环的中奖概率
                $sum -= $value["percent"];
            }
        }
    }
}

思路：参考数学概率论的“黑箱摸球”
总结： 前人实践证实可用且执行效率高，只是概率论学得不好的童鞋理解起来较困难

领悟：好的算法不止要易于理解，还要兼顾执行效率、系统安全和稳健等因素，所以编程之前要开动脑筋、利用手头资源多准备几种算法，综合考虑比较后再做决定