algorithm - 生成实际值列表，总结为固定值并满足一些约束

Question

我需要生成满足以下约束的 n 个随机实数值 P[0]、P[1]、...、P[n-1]:

Pmin[0] <= P[0] <= Pmax[0]
Pmin[1] <= P[1] <= Pmax[1]
...
Pmin[n-1] <= P[n-1] <= Pmax[n-1]

P[0] + P[1] + ... + P[n-1] = S

知道如何有效地做到这一点吗？

Answer 1

一般情况下，如果从给定的范围内均匀地随机选择元素是无法解决这个问题的。

示例 1:假设 Pmin[i] = 0 且 Pmax[i] = 1。假设 n = 10 且 S = 100。那么无解，因为最大可能的和为 10。

例2:假设Pmin[i] = 0且Pmax[i] = 1。假设n = 10且S = 10。那么只有一个解决方案:选择P[i] = 1。

可以编写一个算法，从一组可能的解决方案中随机均匀地选择结果序列；这与说 P[i] 在 Pmin[i] 和 Pmax[i] 之间均匀分布是完全不同的。

基本思路是，在每个阶段，进一步限制你的范围，如下:

1. 范围的开始应该是以下两个量中较大的一个:Pmin[i]，或 S - Smax[i] - P，其中 Smax[i] 是 Pmax[i+1] + 之和。 .. + Pmax[n] 和 P 是总和 P[0] + ... + P[i]。这保证您选择的数字足够大以最终起作用。
2. 范围的末尾应该是以下两个量中较小的一个:Pmax[i]，或 S - Smin[i] - P，其中 Smin[i] 是 Pmin[i+1] + ... + Pmin[n] 的总和，P 与之前相同。这保证您选择的数字足够小以最终起作用。

如果您在选择每个 P[i] 时能够遵守这些规则，那么就会有一个解决方案，并且您会随机找到一个。否则无解。

请注意，要真正随机选择这些解决方案，最好是打乱索引，执行此算法，然后重新排列序列，使其按正确的顺序排列。您可以在 O(n) 中洗牌，执行此算法(此处推荐动态编程，因为您可以自下而上构建解决方案)，然后通过“打乱”结果序列来吐出序列。