微信拼手气红包背后的算法逻辑

偏执的太偏执、 2022-05-30 02:11 246阅读 0赞

## 业务介绍 ##

相信大家都用过微信发红包功能，如下图所示：  
![这里写图片描述][9acb39004d663f132cab23f036e7ded4.png]

两个输入元素：

1、总金额 单位（元）  
2、红包个数

假设输入总金额： **10**，红包个数 **6** ，大家可以试着发一个这样的红包看看，我相信每个人发出去的红包，分配的结果都会不一样，

以A，B，C三人的分配结果做一个示范

A的分配结果是：  
1 ，1， 1， 1， 1， 5

B的分配结果是：  
2，1， 1， 1， 2， 3

C的分配结果是：  
1 ，2， 2， 2， 1， 2

其实真正的分配情况是各种各样的，有无数种的分配结果，这里举例只是大概说了下意思而已。

那么大家有没有思考这背后的分配算法是怎样的呢？

我有思考过这个问题，其实是可以从中找出一些规律出来，在这里分享下我的思考，还望指正。

必要条件：  
1 首先每个红包得到最小金额数至少都是0.01 元（即1分）  
2 其实红包的金额总数加起来肯定等于总金额

有了这两条先决条件，那就好办了

其实思路也很简单

第1步， 首先给每个红包塞入0.01 元，这样剩余总金额就等于 10 - 0.01 \* 6  
第2步，然后循环给每一个红包塞入不等的随机金额，每次塞完就将剩余金额减去已分配的金额，直到剩余金额=0为止，不再塞入为止

## 编码 ##

有了上面思路，加上一点微调，就形成了如下的代码

package com.xyq.maventest.algorithm;
    
    import java.util.Arrays;
    import java.util.Random;
    /****
     * 
     * @author youqiang.xiong
     * <p> 模拟微信发红包的算法封装
     * 
     * </p>
     * 2018年2月25日下午8:04:19
     */
    
    public class RedPacket {
    	
    	
    	public static void main(String[] args) {
    		
    		// 微信红包拆分测试
            double money = 10;  //单位（元）
            int num = 6;
            System.out.println("总金额："+money+"元\t 拆分红包总个数:" + num);
            int[]  array = divived(money,num);
    
            System.out.println("拆分后的各个红包金额数如下:");
            for (int i:array){
                System.out.print((double) i/100+"元\t");
            }
    	}
    
    	/****
         * 微信红包拆分方法
         * @param money  被拆分的总金额 (单位元)
         * @param n    被拆分的红包个数
         * @return  拆分后的每个红包金额数组
         */
        public static int[] divived(double money, int n){
    
            int fen = (int) (money*100);
            if(fen < n || fen < 1){
                throw new IllegalArgumentException("被拆分的总金额不能小于1分");
            }
            // 创建一个长度等于n的红包数组
            int[] array = new int[n];
            //第一步 每个红包先塞1分
            Arrays.fill(array,1);
            //总金额减去已分配的n 分钱
            fen -= n;
            //第二步，循环遍历如果剩余金额>0 则一直分配
            int i = 0;  //从第一个红包进行分配
    
            //创建一个随机分配对象
            Random random = new Random();
            while (fen > 1){
                int f  = random.nextInt(fen);  //创建范围[0,fen)
                array[i++%n] +=  f;
                fen -= f;
            }
    
            //判断剩余未分配的金额是否大于0,如果大于0，可以把剩下未分配金额塞到第一个红包中
            if (fen > 0){
                array[0] +=  fen;
            }
    
            return array;
        }
    }

## 效果 ##

多次运行main方法，控制台每次打印的结果都不一样

第一次运行结果：

总金额：10.0元	 红包总个数:6
    拆分后的各个红包金额数如下:
    5.11元	4.29元	0.26元	0.13元	0.08元	0.13元

第二次运行结果：

总金额：10.0元	 拆分红包总个数:6
    拆分后的各个红包金额数如下:
    9.58元	0.38元	0.01元	0.01元	0.01元	0.01元

第三次运行结果：

总金额：10.0元	 拆分红包总个数:6
    拆分后的各个红包金额数如下:
    9.58元	0.38元	0.01元	0.01元	0.01元	0.01元

第四次运行结果：

总金额：10.0元	 拆分红包总个数:6
    拆分后的各个红包金额数如下:
    1.03元	0.2元	4.91元	3.74元	0.08元	0.04元

不管你多少次，基本上每次运行结果都会不一样。并且这里的分配的策略一定满足两个必要条件。

## TODO ##