部分和問題の3つのアプローチをPythonを用いて実装する

11787 ワード
Python 部分和 競プロ Python テキストリンク

問題概要

n 個の正の整数 a[0],a[1],…,a[n−1] と正の整数 S が与えられる。これらの整数から何個かの整数を選んで総和が S になるようにすることが可能か判定せよ。可能ならば "Yes" と出力し、不可能ならば "No" と出力せよ。

【制約】・1≤n≤10・1≤a[i]≤1000・1≤S≤10000

【数値例】
1)　n=3　a=(7,5,3)　S=10　答え: Yes (7 と 3 を選べばよいです)

2)　n = 2　a=(9,7)　S=6　答え: No

問題概要はけんちょん様のこちらの記事から抜粋させていただいています

iterative(反復的)なアプローチ

from sys import stdin

N, S = map(int, stdin.readline().split())
*A, = map(int, stdin.readline().split())

for i in range(2**N):
    temp_sum = 0
    for j in range(N):
        if ((i >> j) & 1):
            temp_sum += A[j]
    if temp_sum == S:
        print("Yes")
        break
else:
    print("No")

n=3　a=(7,5,3)　S=10の時を具体例を考えてみます。
2**3 = 8 であるので、i は 0~7 の間で探索されます。

全探索した際の表 (1)

ちなみに、以下の内側のfor文については、右シフト演算を繰り返し、右端の数が 1 であればその数を選ぶ、という操作をおこなっています。

N = 3 であるので、j は 0~2 をループします。
j が 0 の時、一番右の数をチェック、
j が 1 の時、真ん中の数をチェック、
j が 2 の時、一番左の数をチェックしています。

for j in range(N):
     if ((i >> j) & 1):
         temp_sum += A[j]

recursive(再帰的)なアプローチ

from sys import stdin

N, S = map(int, stdin.readline().split())
*A, = map(int, stdin.readline().split())

flg = False

def dfs(position, temp_sum):
    global flg

    if position == N-1:
        if temp_sum == S or temp_sum+A[position] == S:
            flg = True
        return

    # 選ぶ場合
    dfs(position+1, temp_sum+A[position])
    # 選ばない場合
    dfs(position+1, temp_sum)

dfs(0, 0)

print("Yes" if flg else "No")

その数を「選ぶ」or「選ばない」を再帰的に繰り返していく解法です。
終了の条件として、postionがN-1,つまり、最後の数を選ぶかどうかに達した際に目標であるSに一致するかどうかを判定しています

Dynamic Programming(動的計画法)によるアプローチ

from sys import stdin

N, S = map(int, stdin.readline().split())
*A, = map(int, stdin.readline().split())

dp = [[True] + [False]*S for _ in range(N)]

for i in range(N):
    for j in range(S+1):
        if j >= A[i]:
            dp[i][j] = dp[i-1][j] or dp[i-1][j-A[i]]
        else:
            dp[i][j] = dp[i-1][j]

print("Yes" if dp[-1][-1] else "No")

n=3　a=(3, 5, 7)　S=10の時をdpの様子を以下に示します

  0    1     2     3    4     5     6     7     8     9     10
3 True False False True False False False False False False False
5 True False False True False True  False False True  False False
7 True False False True False True  False True  True  False True

  • dp[0],つまり最初の行は a = (3) の選び方によってとりえる値をしめしています。
    3を選ぶか、何も選ばないかの2択なので、0, 3のみがTrueとなっています

  • dp[1],つまり、真ん中の行では、a =(3, 5) の選び方によってとりえる値をしめしています。
    3と5を選んだ場合の8,57のみを選んだ場合の5にTrueが追加されていることがわかります。

  • dp[2], つまり、最後の行が、0 ~ 10 までで a = (3, 5, 7) の選び方によってとりえる値をしめしています。
    ここの例では S = 3, 5, 7, 8, 10 がaの選び方によって取りえる値だということがわかります。

最後に

至らぬ点があれば気軽にご指摘お願いします。
一つの問題に対して、一つ解法を実装すると満足しがちですが、あえて複数の解法を考えることは、初心者の自分にとってはとても有効でした!