1

私はいくつかの整数のリストを持っています、例えば[1, 2, 3, 4, 5, 10] そして私は別の整数（N）を持っています。たとえば、N = 19。

整数をリスト内の任意の数の合計として表すことができるかどうかを確認したいと思います。

19 = 10 + 5 + 4

また

19 = 10 + 4 + 3 + 2

リストのすべての番号は1回だけ使用できます。N最大2000以上を調達することができます。リストのサイズは200整数に達する可能性があります。

この問題を解決する良い方法はありますか？

4

3 に答える 3

1

4 年半後、この質問にジョナサンが答えます。Python での 2 つの実装 (ブルートフォースとジョナサン) とそれらのパフォーマンス比較を投稿したいと思います。

def check_sum_bruteforce(numbers, n):
    # This bruteforce approach can be improved (for some cases) by
    # returning True as soon as the needed sum is found;

    sums = []

    for number in numbers:
        for sum_ in sums[:]:
            sums.append(sum_ + number)

        sums.append(number)

    return n in sums


def check_sum_optimized(numbers, n):
    sums1, sums2 = [], []
    numbers1 = numbers[:len(numbers) // 2]
    numbers2 = numbers[len(numbers) // 2:]

    for sums, numbers_ in ((sums1, numbers1), (sums2, numbers2)):
        for number in numbers_:
            for sum_ in sums[:]:
                sums.append(sum_ + number)

            sums.append(number)

    for sum_ in sums1:
        if n - sum_ in sums2:
            return True

    return False


assert check_sum_bruteforce([1, 2, 3, 4, 5, 10], 19)
assert check_sum_optimized([1, 2, 3, 4, 5, 10], 19)

import timeit

print(
    "Bruteforce approach (10000 times):",
    timeit.timeit(
        'check_sum_bruteforce([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 200)',
        number=10000,
        globals=globals()
    )
)

print(
    "Optimized approach by Jonathan (10000 times):",
    timeit.timeit(
        'check_sum_optimized([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 200)',
        number=10000,
        globals=globals()
    )
)

出力 (浮動小数点数は秒):

Bruteforce approach (10000 times): 1.830944365834205
Optimized approach by Jonathan (10000 times): 0.34162875449254027
于 2017-07-31T17:23:33.480 に答える
0

醜い力ずくのアプローチ：

 a = [1, 2, 3, 4, 5, 10]
 b = []
 a.size.times do |c|
    b << a.combination(c).select{|d| d.reduce(&:+) == 19 }
 end
 puts b.flatten(1).inspect
于 2012-12-11T17:57:37.893 に答える