Java实现拼手气红包算法

数据结构与算法 阅读量

实现拼手气红包算法，有以下几个需要注意的地方：

  • 抢红包的期望收益应与先后顺序无关
  • 保证每个用户至少能抢到一个预设的最小金额，人民币红包设置的最小金额一般是0.01元，如果需要发其他货币类型的红包，比如区块链货币或者积分，需要自定义一个最小金额
  • 所有抢红包的人领取的子红包的金额之和加起来，等于发红包的人发出的总红包的金额

下面实现的方式是一次生成所有的子红包，让用户按顺序领取。也可以每领取一个生成一个，两种方式性能上各有优劣。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
private static void randomHandOutAlgorithm(BigDecimal totalAmount, Integer size,
                                    Integer scale, BigDecimal minAmount) {

    //剩余红包金额
    BigDecimal remainAmount = totalAmount.setScale(scale, BigDecimal.ROUND_DOWN);

    //剩余红包个数
    Integer remainSize = size;

    for (int i = 1; i < size; i++) {
        //前n-1个红包的金额，用随机算法
        BigDecimal random = BigDecimal.valueOf(Math.random());
        BigDecimal halfRemainSize = BigDecimal.valueOf(remainSize).divide(new BigDecimal(2), BigDecimal.ROUND_UP);

        //计算单次红包的最大值，该算法也是微信的红包算法，可以保证抢红包的期望收益应与先后顺序无关，但后抢红包的方差更大，因此手气最佳更可能在后抢的人中诞生
        BigDecimal max1 = remainAmount.divide(halfRemainSize, BigDecimal.ROUND_DOWN);

        //同时，最大值需要保证，减去该红包后，剩下的红包足以满足剩余人数的最小金额
        BigDecimal minRemainAmount = minAmount.multiply(BigDecimal.valueOf(remainSize - 1)).setScale(scale, BigDecimal.ROUND_DOWN);
        BigDecimal max2 = remainAmount.subtract(minRemainAmount);

        //最终，单次红包的最大值等于两个最大值中较小的一个
        BigDecimal max = (max1.compareTo(max2) < 0) ? max1 : max2;
        BigDecimal amount = random.multiply(max).setScale(scale, BigDecimal.ROUND_DOWN);
        System.out.println(amount);

        //每个红包的数额不能小于预设的最小金额
        if (amount.compareTo(minAmount) < 0) {
            amount = minAmount;
        }

        remainAmount = remainAmount.subtract(amount).setScale(scale, BigDecimal.ROUND_DOWN);
        remainSize = remainSize - 1;
    }

    //最后一个红包，金额等于剩余金额
    BigDecimal amount = remainAmount;
    System.out.println(amount);
}

最后，未领取的金额需要退回给发红包的用户。写一个定时任务，将未领取的子红包退回即可。

如果在用户每次领取红包的时候生成一个子红包，算法也是一样的，只是每领取一次子红包后，都要更新总红包的余额和剩余数量，然后在退回过期红包时，将总红包的余额退回给发红包的用户即可。

1
2
3
4
5
6
7
randomHandOutAlgorithm(new BigDecimal("5"), 5, 2, new BigDecimal("0.01"));

1.22
0.97
0.60
0.85
1.36