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

問題

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

カードの中から何枚かを選んで、書かれた整数の合計が $ S $ となるときのカードの組み合わせを出力してください。

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

解き方・ソースコード

前回記事では、カードの合計値が $ S $ となるかどうかを判定しました。

今回はカードの合計値 $ S $ になる組み合わせがある場合、そのカードの組み合わせを出力します。

まずは、前回記事と同様に動的計画法を使って合計が $ S $ になるかどうかをチェックします。

この時に作成した $ dp $ を合計値 $ S $ から $ 0 $ にさかのぼって確認すると、選ぶべきカードを復元することができます。

カードを選ぶかどうかは、以下の２条件を確認することで判断します。

　🔹$ dp[x - 1][合計値] = True $ の場合：カード $ x $ を選ばない
　🔹上記以外：カード $ x $ を選ぶ（カードを選んだら、カードの数字を合計値から差し引き、カード $ x $ を保管しておく）

　
[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
25
26
27
28
29
30
31
#--------- 入力例 ----------
N = 5
S = 7
A = [2, 1, 3, 8, 2]
#---------------------------
# 動的計画法（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

# 答えの復元
Answer = []
Place = S
for i in reversed(range(1, N + 1)): # 合計値Sから、1までループ（今回の場合:5,4,3,2,1）
    if dp[i - 1][Place]:
        Place = Place - 0           # カード i を選ばない
    else:
        Place = Place - A[i - 1]    # カード i を選ぶ
        Answer.append(i)

# 答えを出力（インデックスよりカードに書かれた数字を出力）
print('解：', ' '.join(str(A[i - 1]) for i in reversed(Answer)))

[実行結果

解： 2 3 2

[2, 3, 2]という数字の書かれたカードの組み合わせを選ぶと、合計が7になることが分かりました😊