3

自然数を含むセット S と数値であるターゲット t があります。
これらの数値の合計がターゲット t になる可能な組み合わせの数をどのように見つけることができるかを知りたいです。数値は何回でも取得でき、合計がターゲット t に等しく
なるように任意の数を取得できます。

Example
target  6
Set s  {3,8,1,2}
Solution   3+3, 3+2+1, 1+1+1+3, 2+2+2, 2+1+1+2, 2+1+1+1+1, 1+1+1+1+1+1
Total No of solutions possible  7

このための効率的なアルゴリズムは何でしょうか?

4

1 に答える 1

3

ターゲットがかなり小さい場合は、動的計画法を使用して O(|S| * t) の解を得ることができます。Python のサンプル コードは次のとおりです。

def combinations(S, t):
    dp = [1] + [0] * t
    for i in S:
        for j in range(0, t - i + 1):
            dp[j + i] += dp[j]
    return dp[t]
于 2012-08-14T06:27:39.547 に答える