さいきんは競技プログラミングにはまっていて、いわゆる動的計画法の典型、ナップサック問題を解く機会がありました。

問題では最大の価値を出力するケースが多いのですが、気になったので「何を選んだか」を出力する方法について調べてみました。

この記事では２つの方法で何を選んだかを出力する方法をまとめています。

ナップサック問題とは

簡単に概要を書いておきます。

• ナップサックに詰められる最大の重さが与えられる
• 複数の商品の重さと価値が与えられる
• ナップサックに詰められる最大の価値を出力する

AtCoderでは以下のような問題が該当します。

D - Knapsack 1

価値を最大化して出力する

問題にそって以下のようなデータが与えられるとします。

品物の数：3

ナップサックの許容量：8

商品１：重さ 3 価値 30

商品２：重さ 4 価値 50

商品３：重さ 5 価値 60

入力は以下のように与えられます。

3 8
3 30
4 50
5 60

まずはこの形式で最大化された価値を出力してみましょう。

N, W = map(int, input().split())
w_list = [0]
v_list = [0]
for _ in range(N):
    w, v = map(int, input().split())
    w_list.append(w)
    v_list.append(v)

# dp[i][j] i=アイテム番号 j=重さ
# 最大化された価値を記録する
dp = [[0] * (W + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    # いま見ている商品の重さ
    weight = w_list[i]
    # いま見ている商品の価値
    value = v_list[i]
    for j in range(1, W + 1):
        # 重さが足りない場合
        if j < weight:
            # 上の価値を降ろすしかない
            dp[i][j] = dp[i - 1][j]
        else:
            # 加える場合の価値
            add_case = dp[i - 1][j - weight] + value
            # 加えない場合の価値と比較して大きい方を記録
            dp[i][j] = max(dp[i - 1][j], add_case)

print(dp[N][W])
>>>
90

最大の価値は90となりました。

dpテーブルも出力してみます。

print(*dp, sep='\n')
>>>
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 30, 50, 60, 60, 80, 90]

以上のように記録が行われたことが分かります。

何を選んだか確認をする

長くなりましたがここからが本題です。

問題の要件としてはこれで十分ですが、ソースコードに手を加えて、何を選んだか確認できるようにしていきます。

①choiceテーブルを追加する

一つのやり方としてはdpテーブルとは別に何を選んだか記録するテーブルを作ることです。

dpを記録する際に、今見ている商品を採用した場合は1、採用しない場合は0を追加して文字列を作っていきます。

N, W = map(int, input().split())
w_list = [0]
v_list = [0]
for _ in range(N):
    w, v = map(int, input().split())
    w_list.append(w)
    v_list.append(v)

dp = [[0] * (W + 1) for _ in range(N + 1)]
# 0 or 1で何を選んだかを管理する
choices = [[''] * (W + 1) for _ in range(N + 1)]

# テーブルの左側を更新
for i in range(1, N + 1):
    choices[i][0] = '0' * i

for i in range(1, N + 1):
    weight = w_list[i]
    value = v_list[i]
    for j in range(1, W + 1):

        if j < weight:
            dp[i][j] = dp[i - 1][j]
            # 今見ている商品は選べないので0
            choices[i][j] = choices[i - 1][j] + '0'
        else:
            add_case = dp[i - 1][j - weight] + value
            dp[i][j] = max(dp[i - 1][j], add_case)
            # 今見ている商品を選ぶので1
            if add_case > dp[i - 1][j]:
                choices[i][j] = choices[i - 1][j - weight] + '1'
            else:
                # 選ばないので0
                choices[i][j] = choices[i - 1][j] + '0'

print(*choices, sep='\n')
print(choices[N][W])
>>>
['', '', '', '', '', '', '', '', '']
['0', '0', '0', '1', '1', '1', '1', '1', '1']
['00', '00', '00', '10', '01', '01', '01', '11', '11']
['000', '000', '000', '100', '010', '001', '001', '110', '101']
101

1個目と３個目のアイテムを選んで答えにたどり着いた、ということが分かります。

②DPテーブルから復元する

もう一つのやりかたとして、答えから逆算していく、という方法も取れそうです。

記録されたdpテーブルを見てみましょう。

[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 30, 50, 60, 60, 80, 90]

dpの記録される条件はこうなっていました。

if j < weight:
    dp[i][j] = dp[i - 1][j]   
else:
    add_case = dp[i - 1][j - weight] + value
    dp[i][j] = max(dp[i - 1][j], add_case)

• 重さが足りていなかったら今みている商品を使わない（=上の数字を転記）
• 今の商品を使わない場合と使う場合を比較して大きい数字を記録

以下の２パターンで記録をしてきました。

つまり逆からたどる場合は以下のように場合分けすると良いです。

• 上の数字と同じだったらその商品を使っていない
• そうでなければその商品を使っている

プログラムで書くと以下のようになるでしょうか。

# rootの記録
root = []
# 最後の重さ、つまりknapsackの重さW
a_weight = W
# 配列の最後から1番目の商品まで繰り返す
for i in range(N, 0, -1):
    # 上と同じ価値の場合
    if dp[i][a_weight] == dp[i - 1][a_weight]:
        # 今見ている商品は使われていない
        continue
    else:
        # 今見ている商品が使われているためrootに加える
        root.append(i)
        # 重さを引く
        a_weight -= w_list[i]
    # 重さが0になったら見る必要がない
    if a_weight == 0:
        break

print(root)
>>>
[3, 1]

こちらの方法でも1番目と３番目の商品を使ったということが分かりました。

それぞれの評価

①の方は処理が一回で済むのですが、文字列の連結のところがネックとなります。

詳しくは調べていないのですが、Pythonの文字列の+は非破壊的なので、新しいメモリアドレスが占有されます。

hoge='hoge'
print(id(hoge))
hoge+='hoge'
print(id(hoge))
>>>
2211397682928
2211397750512

処理が大量になると、この辺りがパフォーマンスのボトルネックになりそうです。

一方で、②の方はN回のfor loopが追加されていますが、それ以前にN x Wのループが必要なことを考えるとボトルネックにはならなさそうです。

基本的には②の復元方式を使えばよいかなと思います。

おわりに

以上、動的計画法の典型的なナップサック問題についてどれを選んだかを出力するプログラムを紹介しました。

現実のケースで使う際は「何を選んだか」調べるのは必須かなぁと感じています。

引き出しの一つとして持っておいて損はないかとおもいます。