在几个范围内分割一个数字

Question

我试图将一个数字分割成符合预定义范围的较小的数字，而且我似乎无法正确地理解算法。我正在使用C#。

示例

将20分解为三个数字，其中数字必须符合以下范围：1-3、3-10和0-15。最终数字可能如下: 1,5,14或2,3,15

另一个例子可以是将100拆分成四个适合以下范围的数字：0-10、0-10、0-40、0-40。其结果自然是10,10,40,40。在相同的范围内分裂90可产生5、8、38、39等。

你能把我踢向正确的方向吗？

(不，这不是家庭作业，而是个人项目)

Answer 1

您可以使用递归来完成它。

算法的思想是这样的：

• 在每次执行过程中，您将迭代所有可能的间隔数。
• 调用递归以生成下一个间隔的下一个数目。
• 如果在任何时候，该总和超过了所需的值，那么就返回。
• 一旦生成所有的数字，如果和等于所需的数字，那么您就有了一个可能的组合。

这是可以改进的，但这是一个解决办法。

以下代码在控制台中打印所有有效序列：

SplitNumber(100, new Interval[]
{
    new Interval { Min = 0, Max = 11 },
    new Interval { Min = 0, Max = 11 },
    new Interval { Min = 0, Max = 40 },
    new Interval { Min = 0, Max = 40 },
});

public static void SplitNumber(int n, Interval[] intervals)
{
    SplitNumber(n, 0, intervals, "");
}

public static void SplitNumber(int n, int k, Interval[] intervals, string s)
{
    if (n < 0) return;

    if (k >= intervals.Length) { if (n == 0) Console.WriteLine(s); }
    else
        for (int i = intervals[k].Min; i <= intervals[k].Max; i++)
            SplitNumber(n - i, k + 1, intervals, string.Format("{0} {1}", s, i));
}

Interval类如下所示：

public class Interval
{
    public int Min { get; set; }
    public int Max { get; set; }
}

Answer 2

下面描述了一种非常有效的方法，假设桶有某种排序。

首先选择每个范围的最小值并将它们相加。

• 如果和等于你的数字，然后停止。
• 如果和大于您的数字，那么发出一个错误。
• 如果和小于您的数字，然后继续。

接下来，从每个范围减去最小值，使它们都在0上标准化。。从你的号码中减去这笔钱。这并不是绝对必要的，但它有助于解释算法的其余部分。

接下来，执行最大范围值的累积和。找到你的新和合适的水桶(对前一个水桶来说太大了，但适合)。如果没有找到，则发出错误。

然后分配回收箱，使前面的桶达到最大值，并将找到的桶设置为适当的值。

这给出了一组符合条件的值。

如果您希望在范围的“中间”中有更多的值，那么从范围的中间值开始。然后在所有桶中以块加或减值，直到达到最大值为止。这需要更多的迭代，但它也相当有效。

Answer 3

试试这个：

List<KeyValuePair<int, int>> ranges = new List<KeyValuePair<int, int>>();
ranges.Add(new KeyValuePair<int, int>(1, 3));
ranges.Add(new KeyValuePair<int, int>(1, 3));
ranges.Add(new KeyValuePair<int, int>(1, 100));

int totalSum = ranges.Sum(i => i.Value - i.Key);

double ws = 0.0;
int rIndex = 0;
var rangeAndWeight = ranges.Select(i => new { index = rIndex++, range = i, maxw = (ws += (double)(i.Value - i.Key) / totalSum) }).ToList();

int[] nums = ranges.Select(i => i.Key).ToArray();

int number = 50;

Random r = new Random();
while (nums.Sum() != number)
{
    double rDouble = r.NextDouble();

    var index = rangeAndWeight.SkipWhile(i => i.maxw < rDouble).First().index;

    if (nums[index] < ranges[index].Value)
        nums[index] += 1;
}

nums数组包含您需要的较小的数字。