動的計画法（部分和問題）

問題

$ N $ 枚のカードが一列に並べられており、左から $ i $ 番目のカード（カード $ i $ とする）には整数 $ A_i $ が書かれています。

カードの中から何枚かを選んで、書かれた整数の合計が $ S $ となるようにする方法があるかどうかを判定してください。

[制約]
🔹$ 1 \leqq N \leqq 60 $
🔹$ 1 \leqq S \leqq 10000 $
🔹$ 1 \leqq A_i \leqq 10000 $

解き方・ソースコード

動的計画法を使うにあたり、以下のような２次元配列を用意します、

🔹$ dp[i][j]$：カード１、カード２、…、カード $ i $の中から何枚かを選び、選んだカードに書かれた整数の合計を $ j $ にすることが可能かどうか。

まず、$ i=0 $の場合は選んだカードの合計値が必ず$ 0 $になるので、$ dp[0][0] $を $ True $ に設定し、$ dp[0][1] $以降を $ False $ に設定します。

$ i \geqq 1 $の場合、$ dp[i][j] $の状態になる方法つまりカード $ i $ までの中から合計が $ j $ になるように選ぶ方法としては次の２つの方法が考えられます。

🔹方法A：カード$ i - 1 $ の時点で合計が $ j $ であり、カード $ i $ を選ばない。
🔹方法B；カード$ i - 1 $ の時点で合計が $ j - A_i $ であり、カード $ i $ を選ぶ。

方法A・方法Bのうちどちらかが可能であれば、$ dp[i][j] $ の状態にすることができます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#--------- 入力例1 ---------
N = 3
S = 7
A = [2, 2, 3]
#--------- 入力例2 ---------
# N = 3
# S = 6
# A = [2, 2, 3]
#---------------------------
# 動的計画法（i=0）
dp = [[ None ] * (S + 1) for i in range(N + 1)]
dp[0][0] = True
for i in range(1, S + 1):
    dp[0][i] = False

# 動的計画法（i=1）
for i in range(1, N + 1):       # カードの枚数分ループ
    for j in range(0, S + 1):   # 0から合計値Sまでループ
        if dp[i - 1][j] or (j - A[i - 1] > -1 and dp[i - 1][j - A[i - 1]]):
            dp[i][j] = True
        else:
            dp[i][j] = False

print('解：', 'Yes' if dp[N][S] else 'No')

[実行結果（入力例1）]

解： Yes

すべてのカードを選択すると[2 + 2 + 3 = 7]となり、正解はYesとなります。

[実行結果（入力例2）]

解： No

３枚のカードをどう組み合わせても6にはならないので、正解はNoとなります。