最近在微信群里抢红包，经过观察，其规则如下：

¶发红包时

• 总额不得少于份数 * 0.01 元

¶抢红包时

• 每份至少能够分到 0.01 元
• 每份累加起来总是等于总额
• 每份的数额是随机的
• 先抢或后抢并没有明显优势

要如何实现分配算法，能够满足这一需求？

我的第一反应是可以参考遗传算法中的「轮盘赌」权重分配：假定总额为 amount，份数为 n，算法首先随机产生 n 个权重 weight(s)，然后计算权重总和 total，每个领取红包的人得到一个权重 weight_i，然后从总额中取走 weight_i / total * amount 即可。

但由于规则中的货币不可无限细分，而是以 0.01 元为最小单位；此外还要保证每个人至少能得到 0.01 元。所以在取钱的时候要做一些限定：

• 上限不超过 (剩余总额 - (剩余份数 - 1) * 0.01 元)：给后来者留下足够的余额
• 下限不低于 0.01 元：保底安慰奖

以下是用 javascript 写的 demo，为了避免浮点数精度问题，这里的单位为 1 分，即 0.01 元：

var amount = 100; // cent
var n = 10;

var weights = []
var total = 0
for(var i = 0; i < n; i++) {
    var weight = Math.random();
    weights.push(weight);
    total += weight;
}

var balance = amount;
var count = n;

var takes = [];
while(count > 0) {
    var weight = weights[n - count];
    var take = Math.ceil(weight / total * amount);
    take = Math.max(1, Math.min(take, balance - (count - 1)));

    takes.push(take);
    balance -= take;
    count -= 1;
}

// weights
// [0.7933445337694138, 0.0034502430353313684, 0.39447791734710336, 0.29893025243654847, 0.6303203923162073, 0.5726003672461957, 0.9000553076621145, 0.1479424126446247, 0.4969204587396234, 0.4672785080038011]

// takes
// [17, 1, 9, 7, 14, 13, 20, 4, 11, 4]

这一算法有以下优点：

• 随机权重预分配的方法很容易实现；
• 以分为单位，很简单就避开了小数浮点精度问题；
• 保证所有的钱都被取完，总是使用向上取整；
• 上下限的控制保证了规则中最小额度的问题；

用向下取整，最后可能会剩出一些钱，可以留给最后一个人；
用向上取整，最后一个人可能取不到原本应得的额度，但是不需要处理余额；

此外，我也围观了一些别人的思路，除了与我想法相同的以外，还有一些其它的思路：

1. 正态分布：从总额为单位 1 的角度思考，进行随机划分。算法比较复杂，另外还要考虑标准差来影响贫富差距；
2. 先到先得：不作预处理，先抢的人，先从余额里取走随机额度。这种方法可控性太差，有可能出现先抢的人拿走决大部分，而越是后来者只能得越少；

参考资料

• 微信红包的随机算法是怎样实现的？
• 微信红包算法探讨

---

2016-02-29 更新：官方的方案还真的是不作预处理，先到先得: 微信红包的架构设计简介