算法思考：红包金额生成

程序员架构进阶

关注

发布于: 2021 年 04 月 14 日

一背景

最近在整理过去的项目时，回顾了某年红包活动的项目，其中涉及红包金额计算的算法。近些年各家大厂举办的春节红包活动越来越完善，关于活动背后的整体设计介绍、分析、探讨层出不穷。本篇先不关注整体架构，选择红包金额的计算方法作为分析内容。

在当时的项目中，红包金额计算主要是采用了基于一些入参的随机数生成，并且生成的是单个红包金额，并未使用队列方式做预生成。所以再次回顾这个案例，其中其实还有很多可以玩味和深入思考的地方，在这里做一次思考总结。

二题目描述

要求设计在微信群抢红包的算法，红包总金额为 m 元，分成 n 份，要求返回一个红包金额数组。算法需要满足下面的几条要求：

前 n 个抢红包的人都能抢到钱，第 n 个之后的人直接返回空包，所以这里不做考虑；
每个人能抢到的红包金额是随机的，但随机范围最大化(有机会获得可能的最多金额) ；
抢到红包的每个人，抢到相同金额的概率是一样的。

三传说中微信红包算法

网上其实可以搜到很多关于红包金额计算方法的解析，例如微信红包的随机算法是怎样实现的？，给出了一个传说是微信内部人提供的代码：

 public static double getRandomMoney(RedPackage _redPackage){        //remainSize 剩余的红包数量        //remainMoney 剩余的钱        if(_redPackage.remainSize == 1){            _redPackage.remainSize--;            return (double) Math.round(_redPackage.remainMoney * 100)/100;        }        Random r = new Random();        double min = 0.01;        double max = _redPackage.remainMoney / _redPackage.remainSize * 2;        double money = r.nextDouble() * max;        money = money <= min ? 0.01 : mondy;        money = Math.floor(money * 100) / 100;        _redPackage.remainSize--;        _redPackage.remainMoney -= money;        return money;    }

复制代码

当然，double 类型显然是不靠谱的，楼主也做了补充，商业计算需要使用 java.math.BigDecimal；并且在回答中提供了测试结果，包括金额分布情况。

四一个朴素且简单的思考实现

4.1 分析

如果我们自己从头思考，那么会考虑怎样来实现呢？一个简单的方法，n 个人，生成 n 次金额数据，当然，我们也要保证 n 次的金额综合=m 元，且每次每人领取到的金额最小值是 0.01 元，也就是一分钱；最大值是当前的剩余金额-剩余人数。例如总金额 1 元，5 个人可抢，那么第一个人可以抽到的最大金额是 0.96 元，之后每个人领取一元，这是最极端的情况。

其次，上面的这种算法是否能够保证绝对随机？如果不能，那么我们是否有修正策略来做个补救？争取让每个人可能获得的金额尽可能的达到随机效果？

当然，如果能从算法上直接解决是最好的。但如果短时间想不到能够最为符合要求的算法，那么就只能考虑这种补救方法，虽然效率上要差一些，但可以符合要求。既然生成的金额数组可能不是绝对平均，那么我们再生成一次随机数组，调整初始金额数组中各元素的顺序，做个随机乱序，那么就可以接近题目要求的效果。

4.2 一个代码实现（未优化）

public int[] createRandomArr(int m, int n) throws Exception{        int[] ret = new int[n];
        int total = m*100;        Random random = new Random();        int cur = 1;        int curSum = 0;        while(cur <= n-1){            int curLeft = total-curSum-(n-cur);            int curAcount = random.nextInt(curLeft);            curAcount = 1+curAcount;            ret[cur-1] = curAcount;            curSum+=curAcount;            cur++;        }        ret[n-1] = total-curSum;
        int[] newRet = new int[n];        Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();        for(int i=0;i<n;i++){            int index = random.nextInt(n);            while(map.containsKey(index)){                index = random.nextInt(n);            }            newRet[i] = ret[index];            map.put(index, true);        }        return newRet;    }

复制代码

五再次思考

容易看出，上面的算法非常粗糙，不过也勉强能达到题目的大部分要求。影响效率严重的点，就是在生成随机索引数组，也就是第 22 行。上面的示例代码是通过 while 循环来实现的。这里可以考虑通过分段优化的方式来避免 while 循环。事实上，如果 java 中有类似 php 中 shuffle（洗牌，做数组随机乱序）的方法，那么就可以直接使用来做第二步的乱序逻辑了。更多的优化，留给大家来思考了。

发布于: 2021 年 04 月 14 日阅读数: 97

原文链接:【http://xie.infoq.cn/article/362fcaf3a39d9fe8582864661】。文章转载请联系作者。

程序员架构进阶

关注

磨炼中成长，痛苦中前行 2017.10.22 加入

微信公众号【程序员架构进阶】。多年项目实践，架构设计经验。曲折中向前，分享经验和教训

发布

暂无评论

创作场景

算法思考：红包金额生成

一 背景

二 题目描述

三 传说中微信红包算法

四 一个朴素且简单的思考实现

4.1 分析

4.2 一个代码实现（未优化）

五 再次思考

程序员架构进阶

评论

一背景

二题目描述

三传说中微信红包算法

四一个朴素且简单的思考实现

五再次思考