3

一連の整数 (正または負) が与えられた場合、これらの数値の合計が与えられた値になるシーケンスをどのように見つけることができますか?

例: number のリストが与えられた[4,-16, 9, 33]場合、 sum が必要17です。シーケンス[4, 4, 9](番号は再利用できます) またはを選択できます[-16, 33]。シーケンスの長さを減らす効率的な方法を見つけようとしています。

Subset Sum Problem( http://en.wikipedia.org/wiki/Subset_sum )のようですが、私の場合、数字を再利用できます。

また、パーティションの問題 (指定された数に合計されるすべての可能なサブセットを検索する) に少し似ていますが、私の場合は負の値があります。

私の現在の貪欲なアルゴリズムは次のとおりです。各ループで、現在の合計と目標の合計の差を最小限に抑える数値を見つけようとします。

integers = [-2298478782, 1527301251, 4, 4078748803, 3388759435,
        1583071281, 2214591602, 1528349827, -12, 59460983,
        -939524100, -1, 2315255807]
target_sum = 1997393191

difference = target_sum
chain = list()
while difference != 0:
    min_abs_difference = abs(difference)
    next_int = 0
    found = False
    for i in integers:
        new_abs_diff = abs(i+difference)
        if new_abs_diff < min_abs_difference:
            found = True
            next_int = i
            min_abs_difference = new_abs_diff
    if not found:
        print(difference)
        print(chain)
        print("Cannot find an integer that makes difference smaller")
        break
    difference += next_int
    chain.append(next_int)
print(chain)
4

2 に答える 2

1

最適なソリューションを提供する高速なアルゴリズムはおそらくありません。部分和問題は NP 完全であり、その問題はあなたの問題よりも簡単です (数値の再利用を許可するため)。

問題が NP 完全であることを考えると、現在のアルゴリズムの改善に集中するか、C などのより高速な言語で書き直す必要があると思います。その後、Python から C コードを呼び出すことができます。

于 2013-10-29T18:18:11.137 に答える