如何从另一个数组的值中生成一个随机数组，其值的总和在预定的范围内？ 我有一系列正整数，例如[10,25,40,55,80,110]。 我想能够指定一个范围，例如100-150，并从此预先存在的数组中生成一个新数组，其中新的

Question

，并从此预先存在的数组中生成一个新数组，其中新数组值的总和在指定的范围内。原始数组中的值可以在新数组中复制。

例如，阵列

[110]

，

[25, 40, 40]

都是

100-150

的范围的有效阵列。

所有有效的数组都应具有同等的生成概率。

算法应提供类似的随机化，例如我们要生成所有可能的组合，然后在范围内过滤算法，然后从它们中随机选择（这是不可能有效的，因为阵列很大（> 1000）元素）。

我怎么能实现？

我现在正在做的是：

sum = 0
while sum < lower limit of range {
  sum += rand(array)
}

但这只是选择随机数，直到它在范围内。 它给了我很多次的结果，并且超过了范围。

随着这回来，我可以根据我以前的答案在多项式时间内的superexportential人群中发布答案。 首先，您为计算解决方案编写动态编程算法。

def count_subset_sums (array, lower, upper):
    # Start with the empty set.
    sums = {0: 1}
    for i in array:
        next_sums = sums.copy()
        for s, count in sums.items():
            if upper < s + i:
                pass # Skip too large of sums.
            elif s + i not in next_sums:
                next_sums[s + i] = count
            else:
                next_sums[s + i] += count
        sums = next_sums

    answer = 0
    for s, count in sums.items():
        if lower <= s and s <= upper:
            answer += count
    return answer

然后将其转换为捕获解决方案的结构。这是一个相当直的翻译 - 仅因为我添加了一些评论。

def analyze_subset_sums (array, lower, upper):
    sums = {0: SolutionStructure()}

    for i in array:
        next_sums = sums.copy()

        for s, structure in sums.items():
            if upper < s + i:
                pass
            elif s+i in next_sums:
                # choice = this choice
                # prev = prev part of these solution.
                # prev_solutions = solutions found previously
                next_sums[s+i] = SolutionStructure(
                        choice = i,
                        prev = structure,
                        prev_solutions = next_sums[s+i],
                        )
            else:
                next_sums[s+i] = SolutionStructure(
                        choice = i,
                        prev = structure,
                        )
        sums = next_sums

    answer = None
    for s, structure in sums.items():
        if lower <= s and s <= upper:
            if answer is None:
                answer = structure
            else:
                # These have a null choice that will need to be
                # later filtered out.
                answer = SolutionStructure(
                        prev = structure,
                        prev_solutions = answer
                        )
    return answer

然后我们使用它。

def analyze_subset_sums (array, lower, upper):
    sums = {0: SolutionStructure()}

    for i in array:
        next_sums = sums.copy()

        for s, structure in sums.items():
            if upper < s + i:
                pass
            elif s+i in next_sums:
                # choice = this choice
                # prev = prev part of these solution.
                # prev_solutions = solutions found previously
                next_sums[s+i] = SolutionStructure(
                        choice = i,
                        prev = structure,
                        prev_solutions = next_sums[s+i],
                        )
            else:
                next_sums[s+i] = SolutionStructure(
                        choice = i,
                        prev = structure,
                        )
        sums = next_sums

    answer = None
    for s, structure in sums.items():
        if lower <= s and s <= upper:
            if answer is None:
                answer = structure
            else:
                # These have a null choice that will need to be
                # later filtered out.
                answer = SolutionStructure(
                        prev = structure,
                        prev_solutions = answer
                        )
    return answer

在这里是完整的工作计划，包括我以前答案的课程。

Answer 1