分红包，上限是总奖金 30%，下线 1 元，输入奖金总数 m 和人数 n ，输出一个列表表示每个人红包
思路一 传统分红包办法，1 到 n-1 人领随机生成 range （ 1 ，0.3*m ）的红包，最后一个人拿到剩余，但是这样最后一个人可能会超出上下限
思路二 下限当作保底，先每个人分 1 元保底，剩下奖金池是 m-n ，1 到 n-1 人领取随机生成 range （ 0 ，0.3*m-1 ）的红包，最后一个人拿到剩余，这样保证了下限，但是上限还是会超，如果前面 n-1 个人没分完总奖金的（ 1-30%）=70%，剩下一个人就会超过上限 30%
到这里基本时间就到了，感觉凉凉，复盘时候感觉无论怎么随机分，都没法保证刚好分完
思路三是搜索到的一种解法，先计算平均值 avg ，每个人两两一对，领取 avg+-random 的红包，如果人数是单数，则返回平均值。这样能保证分完，不过额真的随机么。
 |
1
phpfpm 5 天前  1
1 先分保底
2 每一块钱 roll ，超过 30%的重新 roll |
 |
2
6HWcp545hm0RHi6G 5 天前
问了下 AI
# 分红包算法思路 ## 问题理解 我们需要将总奖金 `m` 分给 `n` 个人，满足以下条件： 1. 每个人分到的金额不超过总奖金的 30%（即 ≤ 0.3m ） 2. 每个人至少分到 1 元 3. 所有分配金额之和等于总奖金 `m` ## 算法思路 ### 1. 输入验证 首先检查输入是否有效： - 总奖金 `m` 必须 ≥ `n`（因为每人至少 1 元） - 人数 `n` 必须 ≥ 1 ### 2. 初始分配 给每个人分配 1 元（满足下限），剩余金额为 `m - n` ### 3. 分配剩余金额 采用随机分配方法，但要确保每次分配不超过个人上限： - 个人上限为 `min(0.3m - 1, remaining_amount)` - 使用随机算法（如"二倍均值法"）分配剩余金额 ### 4. 具体步骤 1. 初始化每个人为 1 元 2. 计算剩余金额 `remaining = m - n` 3. 当 `remaining > 0`: - 计算当前可分配的最大金额 `max_per_person = min(0.3m - 1, remaining)` - 为每个人随机分配 0 到`max_per_person`之间的金额（或使用其他公平算法） - 确保分配后不超过个人上限和剩余总额 4. 返回分配结果 ## Python 实现示例 ```python import random def distribute_red_packet(m, n): if m < n: raise ValueError("总奖金不能少于人数") if n < 1: raise ValueError("人数必须大于 0") # 每人至少 1 元 result = [1.0 for _ in range(n)] remaining = m - n max_per_person = 0.3 * m - 1 # 个人上限 for i in range(n): if remaining <= 0: break # 当前可分配的最大值 current_max = min(max_per_person, remaining) # 随机分配金额（可以使用更复杂的算法） amount = random.uniform(0, current_max) # 保留两位小数 amount = round(amount, 2) result[i] += amount remaining -= amount # 处理可能的剩余几分钱（由于四舍五入） if remaining > 0: result[0] += round(remaining, 2) # 再次确保没有超过上限 for i in range(n): if result[i] > 0.3 * m: # 调整超出部分 excess = result[i] - 0.3 * m result[i] = 0.3 * m # 将超出部分分配给其他人 for j in range(n): if j != i and result[j] + excess <= 0.3 * m: result[j] += excess excess = 0 break return result ``` ## 注意事项 1. 浮点数精度问题：实际实现中可能需要处理小数点后两位 2. 随机性：可以使用更复杂的随机算法使分配更均匀 3. 边界情况：当 `m` 刚好等于 `n` 时，每人只能得 1 元 4. 当 `0.3m < 1` 时（即 m < 3.33 ），实际上限会高于 30%，这是题目设定导致的矛盾 |
 |
3
Projection 5 天前
先留个保底，然后从 [0, m - n] 区间内随机 n - 1 次划分出 n 个区间，每个人取一个区间 + 保底
|
 |
4
chachi 5 天前
应该有超限重 roll 机制
每个人就 roll 一次就能正好符合我觉着不可能，因为有保底和上限。 |
 |
6
Wxh16144 5 天前 1
|
 |
8
moudy 5 天前
直接生成 n-1 个 0-1 之间的随机数并排序，每个人拿两个相邻随机数差值 x 30%（ m-0.01*n)+0.01
|
 |
9
a0000 5 天前 via Android
先分 1 块钱
每个人在上 0 到 0.3m 减已分奖金之间取随机值，直到总奖金分完，如果没分完，再来多轮 |
 |
10
geelaw 5 天前
问题意思不清楚，需要明确所要的分布，假设：
- 红包金额必须是整数，m 是自然数． - 数据满足 m >= n 且 0.3m >= 1 （其他情况平凡）． - 需要的分布是 X = { (a_1, ..., a_n) | a_i in Z, 1 <= a_i <= 0.3m, sum of a_i = m } 上的均匀分布． 又假设 m, n 不大（具体来说建模为关于 m, n 多项式时间可接受），那么最朴素的思路就是…… 固定 m, n 后，令 f(I, J) = |{ (a_1, ..., a_I) | a_i in Z, 1 <= a_i <= 0.3m, sum of a_i = J }|, 则 f(0, 0) = 1 且 f(0, J) = 0 对所有 J != 0 且 f(I, J) = sum of f(I - 1, J - a_I) over 1 <= a_I <= floor(0.3m). 考虑抽样算法 D(I, J) 表示“I 个人分配 J 元奖金”，则 D(I, J) 是： - 以 f(I - 1, J - x) / f(I, J) 的概率抽取 x ，其中 1 <= x <= 0.3m 且 x in Z ． - 把 x 作为 a_I 输出． - 运行 D(I - 1, J - x)． 所要求的就是运行一次 D(n, m)． ———— 补充细节留给楼主：证明上述 D(n, m) 可以在 (m+n) 的多项式时间内完成． |
|
12
geelaw 5 天前
@geelaw #10 一个简单的优化：D(I, J) 均匀随机出来一个 1 到 f(I, J) 的整数，然后按照 f 做“进位制展开”即可得到一个样本，无需递归/重新采样子问题。
|
 |
13
snailsir 5 天前 via iPhone
|
 |
14
oaix 5 天前
不考虑分布的话，感觉可以这样分：
```python import random def sample(m, n): low = 1 upper = m * 0.3 remain = m result = [] for _ in range(n-1): x = low + min(remain-low, upper) * random.random() remain -= x result.append(x) result.append(remain) random.shuffle(result) return result for i in range(10): print(sample(100, 10)) ``` |
 |
15
renmu 5 天前 via Android
如果最后一个人不符合条件，那就重新 roll
|
 |
16
hxy100 5 天前 3
你们 v 站贴 Python 代码，缩进全无，简直要人命。
|
 |
18
yidinghe 5 天前 via Android
难道不是事先将红包先分好吗？先拆出 n 个红包，这个过程中可以二次调整，随后在领取时随机发。比如你的思路 2 中，发现有超过上限的就将超出部分补给最低的那个就行了。
|
 |
20
sillydaddy 5 天前 via Android
|
 |
21
lzxz1234 5 天前
红包金额从 1 到 x=0.3m ，基于红包 ID 做种子生成 1 到 x 的固定随机数序列共 n 个，每个人按自己随机数占总和的比领钱
|
 |
22
abc634 5 天前
如果没有要求 随机的话，很简单？
上限下限先分好，然后再随机。 1 ， 先每人派发下限, n *1 2 ， 令 (m - n ) = x (0.3m -1) +k, 其中 的商数 x 和余数 k 那么有 x 份上限，以及 剩余金额 k 供剩下的人抽取。 3 ，结果输出：x 份上限，剩下的 n-x 人从 k 里面随机抽取 再加 下限 1 。 |
|
23
abc634 5 天前
补充：追加一个更像随机的 处理：
4 ，x 份上限 可以再和 n-x 中的 x 份 随机配对，然后把他们的金额混合后再随机分配一下。 |
 |
24
kapaseker 5 天前
不能每人一块钱，剩下的给老板吗 ？
|
 |
25
pierswu 5 天前
为什么要领红包得时候，才生成一个随机的金额？
发红包的时候，就按照设计的随机算法，把每个的金额已经生成好了，然后再把超出 30%的匀一下 |
 |
26
winnie2012 5 天前
随机分红包说明奖金不高，直接买点吃的大家一起吃掉。
|
 |
27
InDom 5 天前
先每个人保底分配 1 元, 然后求出剩余奖金的平均值, 然后循环给每个用户随机分配奖金
循环随机分配时随机数动态分配, 每个用户随机范围为 0 到 剩余平均值 + 上次循环剩余奖金, 如果剩余平均值 + 上次循环剩余奖金 > %30-1, 则最小值 + (剩余平均值 + 上次循环剩余奖金 - %30-1). 大概思路如此, 理论上可以保证每次随机都会在上限内分配, 如果上一个人分配的少了, 下一个人就有更高概率分配更多一点. |
 |
28
runlongyao2 5 天前
//m 是金额，n 是人数
(function(m,n){ let result=[] const maxValue = m * 0.3 const _n = Array.from({length:n}).map((_, i) => { return { index: i, value: 1, } }) m = m - n while(m){ const index = getRandomInt(_n.length) _n[index].value++ if(_n[index].value > maxValue){ const removed = _n.splice(index, 1) result.push(removed) } m-- } result = [...result, ..._n].sort((a,b)=>a.index > b.index) return result }(1000,10)) function getRandomInt(max) { return Math.floor(Math.random() * max); } 一块钱一块钱分，您看这样行么。自己写的，还没优化过存储 |
 |
29
InkStone 5 天前
随机+拒绝采样就是最简单也最实用的做法，不用想那么多复杂的……
|
 |
31
chairuosen 5 天前
方法二：第 i 个人并不是 range （ 0 ，0.3*m-1 ），而是 range （ max(0, m-0.3*(n-i)) ，0.3*m-1 ）也就是要保证 i 至少分一个钱数，让后面人卡着最大值能满足不超。当然这样会导致后几个人得到大红包的概率高，只需排好再打乱排序即可
|
 |
32
edward1987 5 天前
你的思路二扩展下就行
思路二 下限当作保底，先每个人分 1 元保底，剩下奖金池是 m-n ，1 到 n-1 人领取随机生成 range （ 0 ，0.3*m-1 ）的红包，最后一个人拿到剩余，这样保证了下限，但是上限还是会超，如果前面 n-1 个人没分完总奖金的（ 1-30%）=70%，剩下一个人就会超过上限 30% [当最后一人超出 30%,则取 30%，多出的金额给剩下的没有达到上限的人随机] 重复操作这个步骤就行 |
 |
33
gxt92 5 天前
想到一种思路🤪
写个 judge 函数，判断方案（顺序领红包金额的数组）是否满足要求 然后死循环 random 出红包队列数组，直到有个数组满足 judge |
 |
34
zoyao 5 天前
1 + ramdom(0, min(0.3m, 剩余奖金))
先分一元，每个人红包最大值就是剩余奖金与总奖金 30%取小值，0~红包最大值取随机数，再加上先分的 1 元 |
 |
36
Yanlongli 4 天前
大脑：这不是简简单单有手就行
手：报错、报错、报错、奖金没分完、奖金分超了、概率不平均 额滴神啊 // php 代码，带 <? 提示 cf 拦截 $fee = 100; // 总奖金 可以是 100k $count = 4; // 不超过 30% 至少要 4 个人及以上 $list = []; $remain = $fee; for ($i = 0; $i < $count; $i++) { $left = $count - $i; $max = min($remain, $fee * 0.3); $min = max(1, $remain - ($left - 1) * $max); $amount = ($i === $count - 1) ? $remain : mt_rand(ceil($min), $max); $list[] = $amount; $remain -= $amount; } // 最后 10w 测试发现，第一个抽的人很亏，所以把所有人的抽奖打乱一下 //第 0 人 => 2049658 //第 1 人 => 2524927 //第 2 人 => 2763712 //第 3 人 => 2761703 shuffle($list); // 当当当当 10w 结果看上去 OK 了 //第 0 人 => 2525703 //第 1 人 => 2524015 //第 2 人 => 2523623 //第 3 人 => 2526659 |
 |
37
littleW2B 4 天前 2
这不就是 softmax 吗。都不用 e ，直接在 0 到 max 之间 random N 个数，然后每个数除以总和乘以红包总额，向下取整，把最后的差额一人一块分了。
|
 |
38
knight618 4 天前
思路就是默认每人一块,剩下的钱一块块的随机给一个人
import random def main(m, n): if m > n >0: m_30 = m * 0.3 print("单人上限:", m_30) if n-1+int(m*0.3) > m or m/n > m_30: # 判定平均分是否会超过 30%等乱七八糟的可能 return [] re_ = [1 for i in range(n)] # 默认每人一块 re_n = [i for i in range(n)] # 分钱团队 m -= n # 去掉默认的钱 while m > 0: # 奖池还有钱 random_n = random.choice(re_n) # 随机没有超过限额的人 re_[random_n] += 1 # 这个人多一块 if re_[random_n] > m_30: # 这个人超过了限额 re_[random_n] -= 1 # 这个人少一块 re_n.pop(re_n.index(random_n)) # 分钱团队删除这个人 continue # 继续分钱 m -= 1 # 奖池减少一块 return re_ elif m == n: return [1 for i in range(n)] else: return [] if __name__ == "__main__": s = 500 # 总奖金 r = 17 # 总人数 result = main(s, r) if result: print(result) else: print("No solution") |
 |
40
senghoo 4 天前
我感觉本质上是一个约束比较宽泛的约束满足问题。与地图填色、八皇后之类的是一类问题。
N 个变量，x_1, x_2,...x_n 有整体约束：x_1+x_2+....x_n=M 变量约束：1<x_i<M/N 然后各类搜索算法跑起来～ |
 |
41
Huelse 4 天前
在创建红包的时候就按数量分好金额池，然后随机抽就完了
|
 |
44
gwbw 4 天前
思路三没什么问题，你可能纠结的"随机"是数学上的随机，工程上只要在最后分的时候把顺序打乱，整体就是公平的。类似于切蛋糕的和分蛋糕的不是同一个人，无论切蛋糕的人怎么切，只要分蛋糕的人闭着眼睛随机分，大家的期望就都一样
|
 |
45
yankebupt 4 天前
哎……多少次了，AI 回答贴个分享链接就行了不要贴结果不要贴结果，又拜拜了一个账号
|
 |
46
yc8332 4 天前
上下限差太多，又限制单包。。基本下限就没用了。
|
 |
48
bloodspasm 4 天前
如果是 2 个人分 100 块钱, 会怎么样? 😅
|
 |
49
vincentWdp 4 天前
1 楼的答案很好啊. 补充一下:
1. 可以先做判断, 对不能满足情况的输入进行报错. 2. 再看 47 楼的回答, 也就是 roll 的时候, 把已经达到上限的元素剔除就好了 |
 |
50
BreadKiller 4 天前
想了一下，感觉只能事先按人数分配好红包金额，不能每次去获取的时候再去计算红包金额。在此前提下，想了一个方案：
首先给每个人分配下限 1 然后循环 每次随机取 1 人 然后再在 0.3m-已分配给这个人的金额 中随机一个金额 判断这个随机金额+已分配金额是否达到 m ，没达到就给这个人分配这个随机的金额，继续循环 如果这个随机金额+已分配金额超过了 m ，那随机金额就取 m-已分配金额，结束循环 用 js 写了一下 金额是乘了 100 用整数算 ``` function calc(m, n) { const min = 100; const max = 0.3 * m; const res = new Array(n).fill(min); let sum = res.reduce((a, b) => a + b, 0); while (sum < m) { const i = Math.floor(Math.random() * n); let rand = Math.floor(Math.random() * (max - res[i])); if (sum + rand > m) { rand = m - sum; } res[i] += rand; sum = res.reduce((a, b) => a + b, 0); } console.log(sum, res); } ``` |
 |
51
lff0305 3 天前
每个人依次生成随机数，如果满足条件且小于剩余钱数，给这个人分钱，对下一个人；
如果到了最后一个人那么判断剩余钱数是否满足条件。如果 OK 那么找到一个方案。否则前一个人重新来 import java.util.Arrays; import java.util.Random; public class RedBag { private Random random = new Random(); public static void main(String[] args) { int[] r = new RedBag().resolve(new int[10], 10,0, 100, 100); System.out.println(Arrays.toString(r)); r = new RedBag().resolve(new int[10], 10, 0, 10, 10); System.out.println(Arrays.toString(r)); } /// result: Result for each persion /// N: Total number of person /// n: Current person, [0, N - 1] /// M: Total money /// m: How much money left private int[] resolve(int[] result, int N, int n, int M, int m) { // Last person, and the left money is OK if (n == N - 1) { if (m >= 1 && m < 0.3 * M) { result[n] = m; return result; } else { return null; } } // left money cannot give at least $1 per person if (m < N - n) { return null; } int value = 0; while (true) { // Try to give some money to current person int range = Math.min(m, (int) Math.floor(0.3 * M)); value = random.nextInt(range) + 1; if (value < m) { result[n] = value; int[] r = resolve(result, N, n + 1, M, m - value); if (r != null) { return r; } } } } } |
 |
52
rainbowhu 3 天前
这样的吗？
对于总量 m 和个数 n ，以及最大比例 r, 每次确定随机范围[x, y] x >= 1 m - x <= (n - 1) * r * m 也即 x >= m - (n - 1) * r * m -> x = max(1, m - (n - 1) * r * m) y <= r * m m - y >= (n - 1) * 1 也即 y <= m - (n - 1) * 1 -> y = min(r * m, m - (n - 1) * 1) |
Select Language