关于随机红包抽奖算法

场景：

　　生成10个随机红包，奖池总金额10000，最小500，最大1000，奖池全部分配完。

　　分析：

　　第一想法简单，直接生成500-1000之间的随机数，直接生成10个，直接上代码。这种写法的问题在于最后一个金额生成的时候会出现问题，会有出现超过最大金额的可能性。

   /**
     *
     * @param lst 生成的奖项列表
     * @param minAmount 红包允许的最小金额
     * @param maxAmount 红包允许的最大金额
     * @param totalAmount 总奖池金额
     * @param count 生成红包数量
     */public void generateRoundAmount(List<Integer> lst, Integer minAmount, Integer maxAmount, Integer totalAmount, Integer count){
        for (int i = 1; i <= count ; i++) {
            //当前理论允许的最大金额， 保证后续每人持有最小
            Integer tmpMax =  totalAmount - minAmount * (count - i);
            //前4成的最大金额，为理论最大金额的一半， 防止前面金额过大，后面全是1
            tmpMax = i <= Math.round(count*0.4) ? tmpMax/2 : tmpMax;
            //当有传入最大金额，且小于当前理论最大金额， 则取最大金额，否则取理论最大金额
            tmpMax = maxAmount != null && tmpMax > maxAmount ? maxAmount : tmpMax;
            //当最后一个的时候，全部归其所有， 否则取随机数区间[min, max]
            Integer tmpValue = i == count ? totalAmount : StringUtil.getRandomNumberBetween(minAmount, tmpMax); 
            lst.add(tmpValue);
            //减去已抽取金额
            totalAmount = totalAmount - tmpValue;
        }
    }

　　解决方法有两种：

　　第一种方法，判断最后一个金额大于maxAmount，则重新运行，直到出现最后一个金额小于等于maxAmount即可。当然这种方法比较笨，并不推荐。

　　第二中方法，就是剩余的金额，继续在已经生成的奖项列表中分配（未超过最大金额的项）。

　　改造下方法

 /**
     *
     * @param lst 生成的奖项列表
     * @param minAmount 红包允许的最小金额
     * @param maxAmount 红包允许的最大金额
     * @param totalAmount 总奖池金额
     * @param count 生成红包数量
     */
    @Override
    public void generateRoundAmount(List<Integer> lst, Integer minAmount, Integer maxAmount, Integer totalAmount, Integer count){
        Integer remainingAmount = 0; //剩余金额， 默认0
        //判断下， 红包溢出和不足都不允许， 等于的情况此处也不考虑
        if(maxAmount * count <= totalAmount || minAmount * count >= totalAmount){
            throw new BaseException("数据错误，请调整红包数量或最大金额上限");
        }
        
        for (int i = 1; i <= count ; i++) {
            //当前理论允许的最大金额， 保证后续每人持有最小
            Integer tmpMax =  totalAmount - minAmount * (count - i);
            //前4成的最大金额，为理论最大金额的一半， 防止前面金额过大，后面全是1 -- 可忽略不要此行
            tmpMax = i <= Math.round(count*0.4) ? tmpMax/2 : tmpMax;
            //当有传入最大金额，且小于当前理论最大金额， 则取最大金额，否则取理论最大金额
            tmpMax = maxAmount != null && tmpMax > maxAmount ? maxAmount : tmpMax;

            if(i == count && maxAmount != null && totalAmount > maxAmount){
                //最后一个红包数量大于最大允许金额, 计算出剩余金额
                lst.add(maxAmount);
                remainingAmount = totalAmount - maxAmount;
            } else{
                Integer tmpRandomInt = StringUtil.getRandomNumberBetween(minAmount, tmpMax);
                lst.add(tmpRandomInt);
                //奖池金额为总金额减去已抽取金额
                totalAmount = totalAmount - tmpRandomInt;
            }
        }
        //剩余金额大于0则继续分配
        while(remainingAmount > 0){
            remainingAmount = addAmountToList(lst, maxAmount, remainingAmount);
        }
    }

    /**
     *
     * @param lst
     * @param maxAmount 允许最大金额
     * @param totalAmount 可分配金额
     */
    private Integer addAmountToList(List<Integer> lst, Integer maxAmount, Integer totalAmount){
        for (int i = 0; i < lst.size(); i++) {
            if (totalAmount <= 0){
                break;
            }
            if (lst.get(i) < maxAmount){ //当列表中的金额小于最大金额时， 才分配
                //临时最大允许金额
                Integer tmpMax = maxAmount - lst.get(i) > totalAmount ? totalAmount : maxAmount - lst.get(i);
                Integer tmpRandomInt = StringUtil.getRandomNumberBetween(1, tmpMax);
                lst.set(i, lst.get(i) + tmpRandomInt);
                totalAmount = totalAmount - tmpRandomInt;
            }
        }
        return totalAmount;
    }

　　至此可以解决问题。

　　还想到个问题，既然需要循环去分配，不如再简化一点，首先给列表分配允许最小额度的红包，再循环分配。继续改造下此方法

    /**
     *
     * @param lst 生成的奖项列表
     * @param minAmount 红包允许的最小金额
     * @param maxAmount 红包允许的最大金额
     * @param totalAmount 总奖池金额
     * @param count 生成红包数量
     */
    @Override
    public void generateRoundAmount(List<Integer> lst, Integer minAmount, Integer maxAmount, Integer totalAmount, Integer count){
        //判断下， 红包溢出和不足都不允许,  等于的情况是允许的
        if(maxAmount * count < totalAmount || minAmount * count > totalAmount){
            throw new BaseException("数据错误，请调整红包数量或最大金额上限");
        }
        //如果最大金额*数量=奖池金额，直接全是最大的，因为奖池最终是要分配完的
        if (maxAmount * count == totalAmount){
            minAmount = maxAmount;
        }
        for (int i = 1; i <= count ; i++) {
            lst.add(minAmount);
        }
        Integer remainingAmount = totalAmount - minAmount * count;
        //剩余金额大于0则继续分配
        while(remainingAmount > 0){
            remainingAmount = addAmountToList(lst, maxAmount, remainingAmount);
        }
        //此方法可随机打乱列表排序
        //Collections.shuffle(lst);
    }

搞定，ps，此处考虑的是奖池全分配完的情况。

关于随机红包抽奖算法

推荐阅读