|
问题意思不清楚，需要明确所要的分布，假设：
- 红包金额必须是整数，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) 的多项式时间内完成． |
