Python3で実装問題解決力を鍛える！アルゴリズムとデータ構造【第５章】設計技法(3)：動的計画法

「問題解決力を鍛える！アルゴリズムとデータ構造」の章末問題をPython3で実装していくシリーズ。

大枠まとめ記事は、ここに。 blacktanktop.hatenablog.com

前回の記事は、【第４章】設計技法(2)：再帰と分割統治法

blacktanktop.hatenablog.com

今回は【第５章】設計技法(3)：動的計画法について扱うちょっとボリューム多いし、まだ途中。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

作者:大槻兼資
発売日: 2020/10/02
メディア: 単行本（ソフトカバー）

内容
【第５章】設計技法(3)：動的計画法の概要
章末問題
まとめ
終わりに

内容

Python3でやっている。
簡単に自分の理解を整理する用。
そこまで厳密ではない可能性が高い。
記事を書いたら、書評の方に記事を載せていく。
コード等はGitHubにおいた。 github.com

【第５章】設計技法(3)：動的計画法の概要

章末問題

5.1 2つの要素をDPで取り扱う

入力は以下を想定して、

$dp[i]$ を $i$ 日目までに得られる幸福度の和の最大値としたいけど、それではダメ。
なぜなら、「連続で同じ行動をとることができない」という制約があるため。
当日に大きい値を選びたいけど、前日選んでたら選べない。
なので、 $dp[i][j]$ のようにして、 $i$ 日目に行動 $j$ をして、 $i$ 日目までに得られる幸福度の和の最大値とする方針で実装する。

def main():
    n = int(input())
    abc = [list(map(int, input().split())) for _ in range(n)]
    # dp[i][0or1or2]のような形にして、i+1日目にある行動をした時の最大値という意味
    # a, b, c = 0, 1, 2 として扱う
    # dp[3][2]なら4日目にCをした時の最大値
    # dpの枠の用意
    dp = [[0] * 3 for _ in range(n)]
    # dpの初期値
    # 1日目の幸福度
    for i in range(3):
        dp[0][i] = abc[0][i]
    print('初期値(1日目)代入', dp)
    # 2日目以降のdpを代入
    # 当日のある行動の値は、前日の当日の行動でない残りのどちらかの行動 + ある行動の値
    for i in range(1, n):
        dp[i][0] = max(dp[i-1][1] + abc[i][0], dp[i-1][2] + abc[i][0])
        dp[i][1] = max(dp[i-1][0] + abc[i][1], dp[i-1][2] + abc[i][1])
        dp[i][2] = max(dp[i-1][0] + abc[i][2], dp[i-1][1] + abc[i][2])
        print(i, '日目の行動を考慮した',  i+1, '日目の行動別最大幸福', dp)
    # dpの最後の値の最大値が幸福度最大
    ans = max(dp[n-1])
    print(n, '日間の幸福度の最大値', ans)
if __name__ == '__main__':
    main()

5.2 部分和問題をDPで解く

$n$ 個の正の整数列 $a$ と正の整数 $w$ と正の整数 $k$ が与えられる。
これらの整数から何個かの整数を選んだ総和が $w$ になるかどうか。

4章と同じく部分和問題なので、入力は以下を想定して、

4 14
3 2 6 5

nn 個の正の整数 a[0],a[1],…,a[n−1]a[0],a[1],…,a[n−1] と正の整数 AA が与えられる。
これらの整数から何個かの整数を選んで総和が AA になるようにすることが可能か判定する。
可能ならば "YES" と出力し、不可能ならば "NO" と出力せよ。
$dp[i+1][j]$ は $a$ の(indexとして) $i$ 番目までの整数の中からいくつか選んで総和を $j$ とすることができるかどうか(できるなら1, できないなら0)
初期条件は $0$ 個の整数の和は $0$ なので、 $dp[0][0]$ = 1
を用いて、の値を以下のように更新していく。
- 整数を選ばない場合
  - $dp[i][j]$ が1なら、 $dp[i+1][j]$ = 1
- 整数を選ぶ場合 ( )
  - $dp[i][j-a[i]]$ が1なら、 $dp[i+1][j]$ = 1
これを実装する。
- 入力の数値をindexに合わせる方がいいので、dpのリストはn+1, w+1の多重リストにする。

def main():
    n, w = map(int, input().split())
    a = [int(x) for x in input().split()]
    print('a:', a)
    # dp[i+1][j]はi番目(indexにおいて)までの整数の中からいくつか選んで総和jにできるかという意味
    # dp[3][2]ならaの2番目(indexにおいて)までの整数の中からいくつか選んで合計が2になるなら1とする
    # dpの枠の用意(indexとn, wを合わせるので+1する)
    dp = [[0] * (w+1) for _ in range(n+1)]
    # dpの初期値(0個から0は作れるので)
    dp[0][0] = 1
    # ２重のfor文でO(nw)
    for i in range(n):
        for j in range(w+1):
            # a[i]を選ばない場合
            if dp[i][j]:
                dp[i+1][j] = dp[i][j]
                print(a[:i+1], 'の中の整数のいくつかで', j, 'が作れるか')
                print(dp)
            # a[i]を選ぶ場合
            if j >= a[i] and dp[i][j-a[i]]:
                    # a[i]を選んで成立するには
                    # dp[i][j-a[i]]がTrueである必要がある
                    dp[i+1][j] = dp[i][j-a[i]]
                    print(a[:i+1], 'の中の整数のいくつかで', j, 'が作れるか')
                    print(dp)
    if dp[n][w]:
        print(a[:i+1], 'の中の整数のいくつかで', j, 'が作れるか')
        print('Yes')
    else:
        print(a[:i+1], 'の中の整数のいくつかで', j, 'が作れるか')
        print('No')
    print('forの回転数は', (i+1) * j)
    print('n x w　は', n * w)
    
if __name__ == '__main__':
    main()

5.3 部分和問題（総和として得られる数の種類数）

少し問題が変更。得られる総和が成立するパターン数を数えることで、結果的にどんな値が総和として得られるのかを把握する。 * $n$ 個の正の整数列 $a$ と正の整数 $w$ が与えられる。
* これらの整数から何個かの整数を選んだ総和が $1$ 以上 $w$ 以下の整数が何通りあるかを求めよ。

$dp[i+1][j]$ は $a$ の(indexとして)i番目までの整数の中からいくつか選んで総和をjとすることができる組み合わせの数
初期条件は $0$ 個の整数の和は $0$ なので、 $dp[0][0]$ = 1。他は0
を用いて、の値を以下のように更新していく。
- 整数を選ばない場合
  - $dp[i][j]$ 通りを加える
- 整数を選ぶ場合 ( )
  - $dp[i][j-a[i]]$ 通りを加える。
これを実装する。
$dp[n][w]$ はどの値が、どのくらいの組み合わせ数あるかと言う意味で、今回は1以上のものが得られる数ということになる。
最後に $dp[n][w]$ のリストの中で0でないものをカウントする。ただし、 $dp[n][0]$ の1は除く。

def main():
    n, w = map(int, input().split())
    a = [int(x) for x in input().split()]
    print('a:', a)
    # dp[i+1][j]はi番目(indexにおいて)までの整数の中からいくつか選んで総和jにできる組み合わせの数
    # dp[3][2]ならaの2番目(indexにおいて)までの整数の中からいくつか選んで合計が2になる組み合わせの数
    # dpの枠の用意(indexとn, wを合わせるので+1する)
    dp = [[0] * (w+1) for _ in range(n+1)]
    # dpの初期値(0個から0は作れるので)
    dp[0][0] = 1
    # ２重のfor文でO(nw)
    for i in range(n):
        for j in range(w+1):
            # a[i]を選ばない場合
            dp[i+1][j] += dp[i][j]
            # a[i]を選ぶ場合
            if j >= a[i]:
                dp[i+1][j] += dp[i][j-a[i]]
    print('===============================================')
    print('0以上W以下に一致する組み合わせ数のそれぞれの数は', dp[n])
    print('1以上W以下で作ることができる整数の種類数は', sum([1 for i in dp[n] if i > 0]) - 1)
    print('===============================================')
    print('forの回転数は', (i+1) * j)
    print('n x w　は', n * w)
if __name__ == '__main__':
    main()

5.4 部分和問題（5.2に選べる数に制約があるパターン）

$n$ 個の正の整数列 $a$ と正の整数 $w$ と正の整数 $k$ が与えられる。
これらの整数から $k$ 個の整数を選んだ総和が $w$ になるかどうか。

普通に $dp[n][w][k]$ みたいにやろうとすると、計算量が増えるので、以下のようにやる。

$dp[i+1][j]$ は $a$ の(indexとして) $i$ 番目(indexにおいて)までの整数の中からいくつか選んで総和 $j$ にできる方法をすべて考えたときに選んだ整数の個数の最小値とする。
初期条件は $0$ 個の整数の和は $0$ なので、 $dp[0][0]$ = 0。他はinfとする。（とても大きい数にする）
を用いて、の値を以下のように更新していく。
- 整数を選ばない場合
  - $dp[i][j]$ を代入
- 整数を選ぶ場合 ( )
  - $dp[i][j]$ と $dp[i][j-a[i]] + 1$ の小さい方を代入
これを実装する。

def main():
    n, w, k = map(int, input().split())
    a = [int(x) for x in input().split()]
    print('w', w)
    print('k', k)
    print('a:', a)
    # dp[i+1][j]はi番目(indexにおいて)までの整数の中からいくつか選んで総和jにできる方法をすべて考えたときに選んだ整数の個数の最小値
    # dpの枠の用意(indexとn, wを合わせるので+1する)
    # 
    INF = float('inf')
    dp = [[INF] * (w+1) for _ in range(n+1)]
    # dpの初期値(kは1以上で)
    dp[0][0] = 0
    # ２重のfor文でO(nw)
    for i in range(n):
        for j in range(w+1):
            # a[i]を選ばない場合
            dp[i+1][j] = dp[i][j]
            # a[i]を選ぶ場合
            if j >= a[i]:
                dp[i+1][j] = min(dp[i][j], dp[i][j-a[i]] + 1)
    print('===============================================')
    print(a, 'から', k, '個以下を選んで総和を', w, 'にした時の整数の個数の最小値は', dp[n][w])
    print(a, 'から', k, '個以下を選んで総和を', w, 'にできるか？')
    if dp[n][w] <= k:
        print('Yes')
    else:
        print('No')
    print('===============================================')
    print('forの回転数は', (i+1) * j)
    print('n x w　は', n * w)
if __name__ == '__main__':
    main()

5.5 部分和問題（個数制限なし）

5.6 部分和問題（個数制限あり）

5.7 最長共通部分列問題

5.8 区間DP

5.9 Slimes

まとめ

DPは漸化式・初期条件をいかにうまく設定するかがポイント
- 5.4みたいに3条件にしちゃうと計算量ふえるから、定義を変えるなど。

終わりに

積極的に、DPの問題は余り解いてこなかったが、パターン分けされていて、頭に入った。コード書くのも少し慣れたが、もう少し時間をかけて取り組む。