ナップサック問題（動的計画法⑧）

December 21, 2022

問題

N 個の品物があります。 品物には 1,2,…,N と番号が振られています。

各 i (1≦i≦N) について、品物 i の重さは w_i で、価値は v_iです。

N 個の品物のうちいくつかを選び、ナップサックに入れて持ちかえります。 

ナップサックの容量は W であり、持ち帰る品物の重さの総和は W 以下でなければなりません。

持ち帰る品物の価値の総和の最大値を求めてください。

解法・ソースコード

今回は、もっとも単純な ナップサック問題 のおさらいです。

品物ごと、許容範囲の重さごと にループを回して、品物を入れるか入れないかを選択し、価値の高くなる方の選択結果を メモ化テーブル に格納していきます。

[Google Colaboratory]

#--------- 入力例1 ----------
w = 8
items = [{'weight':3, 'value':30},
         {'weight':4, 'value':50},
         {'weight':5, 'value':60}]
#--------- 入力例2 ----------
# w = 5
# items = [{'weight':1, 'value':1000000000},
#          {'weight':1, 'value':1000000000},
#          {'weight':1, 'value':1000000000},
#          {'weight':1, 'value':1000000000},
#          {'weight':1, 'value':1000000000}]
#--------- 入力例3 ----------
# w = 15
# items = [{'weight':6, 'value':5},
#          {'weight':5, 'value':6},
#          {'weight':6, 'value':4},
#          {'weight':6, 'value':6},
#          {'weight':3, 'value':5},
#          {'weight':7, 'value':2}]
#----------------------------
n = len(items)    # 品物の総数

# メモ化テーブル（動的計画法用）
memo = {}

for i, item in enumerate(items):    # 品物ごとにループ
    for j in range(w + 1):          # 重さ＋1までループ
        if j < items[i]['weight']:          # 重さが許容範囲外の場合
            # 品物を入れない
            memo[i + 1, j] = memo.get((i, j), 0)
        else:                               # 重さが許容範囲内の場合
            # 品物を入れない場合
            a = memo.get((i, j), 0)
            # 品物を入れる場合（許容範囲の重さを減らし、価値を増やす）
            b = memo.get((i, j - items[i]['weight']), 0) + items[i]['value']
            memo[i + 1, j] = max(a, b)    # 価値が高いほうを選択

print('【メモ化テーブルの内容】')
for i, item in enumerate(items):    # 品物ごとにループ
    for j in range(w):              # 重さごとにループ
        print(str(memo[i+1, j+1]).rjust(2, ' '), end=' ')
    print()
print('-----------------------')
print('解（価値の総和の最大値）：', memo[len(items), w])

[実行結果(入力例1)]

【メモ化テーブルの内容】
 0  0 30 30 30 30 30 30 
 0  0 30 50 50 50 80 80 
 0  0 30 50 60 60 80 90 
-----------------------
解（価値の総和の最大値）： 90

品物 1,3 を選ぶと、重さの総和は 3+5=8 となり、価値の総和は 30+60=90 となります。

[実行結果(入力例2)]

【メモ化テーブルの内容】
1000000000 1000000000 1000000000 1000000000 1000000000 
1000000000 2000000000 2000000000 2000000000 2000000000 
1000000000 2000000000 3000000000 3000000000 3000000000 
1000000000 2000000000 3000000000 4000000000 4000000000 
1000000000 2000000000 3000000000 4000000000 5000000000 
-----------------------
解（価値の総和の最大値）： 5000000000

全部の品物 を持っていくことができるので、価値の総和は 5000000000 となります。

[実行結果(入力例3)]

【メモ化テーブルの内容】
 0  0  0  0  0  5  5  5  5  5  5  5  5  5  5 
 0  0  0  0  6  6  6  6  6  6 11 11 11 11 11 
 0  0  0  0  6  6  6  6  6  6 11 11 11 11 11 
 0  0  0  0  6  6  6  6  6  6 12 12 12 12 12 
 0  0  5  5  6  6  6 11 11 11 12 12 12 17 17 
 0  0  5  5  6  6  6 11 11 11 12 12 12 17 17 
-----------------------
解（価値の総和の最大値）： 17

品物 2,4,5 を選ぶと、重さの総和は 5+6+3=14 で価値の総和は 6+6+5=17 となります。

夏休み（動的計画法⑦）

December 20, 2022

問題

 N 日の夏休みがあります。
 
各 i (1 ≦ i ≦ N) について、i 日目には次の活動のうちひとつを選んで行います。

　A: 海で泳ぐ。 幸福度 a_i を得る。

　B: 山で虫取りをする。 幸福度 b_i を得る。
　
　C: 家で宿題をする。 幸福度 c_i を得る。

2 日以上連続で同じ活動を行うことはできません。

幸福度の 総和の最大値 を求めてください。

解法・ソースコード

Ｎ日目にそれぞれの活動を行った場合の幸福度を管理するためのメモ化テーブル（動的計画法のための２次元配列）を用意します。

i - 1日目に jの活動、i日目に kの活動 を行う場合の 幸福度memo1 を計算し、一番大きいものを memo[i + 1][k] に代入します。

[Google Colaboratory]

#--------- 入力例1 ----------
lst = [(10, 40, 70),
       (20, 50, 80),
       (30, 60, 90)]
#--------- 入力例2 ----------
# lst = [(100, 10, 1)]
#--------- 入力例3 ----------
# lst = [(6, 7, 8),
#        (8, 8, 3),
#        (2, 5, 2),
#        (7, 8, 6),
#        (4, 6, 8),
#        (2, 3, 4),
#        (7, 5, 1)]
#----------------------------
n = len(lst)    # 夏休みの日数
# メモ化テーブル（動的計画法用の2次元配列。第１引数：夏休みの日数＋１日、第２引数：３つの活動）
memo = [[0 for i in range(3)] for j in range(n + 1)]

for i in range(n):          # 夏休みの日数分ループ
    for j in range(3):      # 前日の活動 
        for k in range(3):  # 当日の活動
            if j == k:      # 前日と同じ活動はできない
                continue
            # i-1日目(前日)にjの活動、i日目にkの活動を行う場合の幸福度
            memo1 = memo[i][j] + lst[i][k]
            # memo[i + 1][k]はi日目にkを行ったときの得られる累積の最大幸福度
            memo[i + 1][k] = max(memo[i + 1][k], memo1)

for i in range(n + 1):
    print(f'{i}日目の累積最大幸福度', memo[i])
print('解（幸福度の総和の最大値）：',max(memo[n]))

[実行結果(入力例1)]

0日目の累積最大幸福度 [0, 0, 0]

1日目の累積最大幸福度 [10, 40, 70]

2日目の累積最大幸福度 [90, 120, 120]

3日目の累積最大幸福度 [150, 180, 210]

解（幸福度の総和の最大値）： 210

C, B, C の順に活動を行うと、幸福度の総和は 70 + 50 + 90 = 210 となります。

[実行結果(入力例2)]

0日目の累積最大幸福度 [0, 0, 0]

1日目の累積最大幸福度 [100, 10, 1]

解（幸福度の総和の最大値）： 100

A の活動を行うと最大幸福になるのは明らかです。

[実行結果(入力例3)]

0日目の累積最大幸福度 [0, 0, 0]

1日目の累積最大幸福度 [6, 7, 8]

2日目の累積最大幸福度 [16, 16, 10]

3日目の累積最大幸福度 [18, 21, 18]

4日目の累積最大幸福度 [28, 26, 27]

5日目の累積最大幸福度 [31, 34, 36]

6日目の累積最大幸福度 [38, 39, 38]

7日目の累積最大幸福度 [46, 43, 40]

解（幸福度の総和の最大値）： 46

C, A, B, A, C, B, A の順に活動を行えば最大幸福になります。

文字列判定（動的計画法⑥）

December 19, 2022

問題

英小文字の文字列 Ｓ があります。

空文字 Ｔ に対して次の操作を繰り返すことで、Ｓ＝Ｔ である状態にできるかどうかを判定してください。

「Ｔ の末尾に"dream"、"dreamer"、"erase"、"eraser"のいずれかを追加する」

解法・ソースコード

まず 再帰関数 を用いた 全探索解法 を考えます。

次のように 再帰関数 を定義します。

rec(i) ← 文字列Ｓの最初のｉ文字分が、"dream"、"dreamer"、"erase"、"eraser"の連結で作れるかどうかを表すブール値（True／False）

文字列Ｓの長さをＮとしたとき、rec(n)が最終的な答えとなります。

rec(i)を求めるために、次の４パターンに分けて考えます。

s[0:i]の末尾を”erase”で区切る場合
rec(i - 5)がTrue かつ s[0:1]の最後の５文字が”erase”であるならば、rec(i)はTrue
s[0:i]の末尾を”eraser”で区切る場合
rec(i - 6)がTrue かつ s[0:1]の最後の５文字が”eraser”であるならば、rec(i)はTrue
s[0:i]の末尾を”dream”で区切る場合
rec(i - 5)がTrue かつ s[0:1]の最後の５文字が”dream”であるならば、rec(i)はTrue
s[0:i]の末尾を”dreamer”で区切る場合
rec(i - 7)がTrue かつ s[0:1]の最後の５文字が”dreamer”であるならば、rec(i)はTrue

この 再帰関数 rec(i) を踏まえて、動的計画法 を表す 配列memo を次のように定義します。

memo[i] ← s[0:i]が、"dream"、"dreamer"、"erase"、"eraser"の連結で作れるどうかを表すブール値（True／False）

memo[0]、memo[1]、…、memo[n] の値を順番に求めていきます。

[Google Colaboratory]

#---------- 入力例 ----------
s = 'erasedream'
#----------------------------
n = len(s)      # 文字列の長さ
memo = [False] * (n + 1)    # メモ化テーブル（動的計画法用の配列）
memo[0] = True

# memo[0]、memo[1]、…、memo[n]を順に求める
for i in range(n + 1):
    if i >= 5 and memo[i - 5] and s[i - 5:i] == 'erase':
        print(i, 'erase')
        memo[i] = True
    if i >= 6 and memo[i - 6] and s[i - 6:i] == 'eraser':
        print(i, 'eraser')
        memo[i] = True
    if i >= 5 and memo[i - 5] and s[i - 5:i] == 'dream':
        print(i, 'dream')
        memo[i] = True
    if i >= 7 and memo[i - 7] and s[i - 7:i] == 'dreamer':
        print(i, 'dreamer')
        memo[i] = True
print('memo', memo)
print('解：Yes' if memo[n] else '解：No')

[実行結果]

5 erase

10 dream

memo [True, False, False, False, False, True, False, False, False, False, True]

解：Yes

“erase” + “dream” で、“erasedream” という文字列が作成できるので、正解は “Yes”（作成できる） となります。

カエルの段差移動2（動的計画法⑤）

December 18, 2022

動的計画法

カエルが最小コストで段差を移動する問題の２つめを、動的計画法 を使って解いていきます。

[問題]

Ｎ個の足場があります。 足場には 1, 2, …, N と番号が振られています。

各 i (1 ≦ i ≦  N) について、足場 i の高さは h_i です。

最初にカエルは、足場1にいます。

カエルは次の行動を何回か繰り返し、足場Ｎまで辿り着こうとしています。

足場 i にいるとき、足場 i + 1, i + 2, …, i + K のどれかへジャンプする。 

このとき、ジャンプ先の足場を j とすると、コスト ∣h_i − h_j∣ (差分の絶対値)を

コストとして支払う必要があります。

カエルが足場 N に辿り着くまでに支払うコストの 総和の最小値 を求めてください。

解法・ソースコード

前回の問題との違いは、ジャンプする幅が i+1, i+2 だけではなく、i + K と可変になっているところです。

ただし、前回の処理で +1, +2 の２パターンで処理していた個所を、K回ループで回す 処理に変えるだけなので、ほんの少しの修正で対応することが可能です。

修正したソースコードは次のようになります。

[Google Colaboratory]

#--------- 入力例1 ----------
k=3
lst = [10, 30, 40, 50, 20]
#--------- 入力例2 ----------
# k=1
# lst = [10, 20, 10]
#--------- 入力例4 ----------
# k=100
# lst = [10, 10]
#--------- 入力例4 ----------
# k=4
# lst = [40, 10, 20, 70, 80, 10, 20, 70, 80, 60]
#----------------------------
n = len(lst)      # 段差の数

memo = [float('inf')] * n

memo[0] = 0
for i in range(n):
    for x in range(1, k + 1):
        if i - x >= 0:
            memo[i] = min(memo[i], memo[i - x] + abs(lst[i] - lst[i - x]))
print(memo[n-1])

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

足場 1 → 2 → 5 と移動すると、コストの総和は ∣ 10 − 30 ∣ + ∣ 30 − 20 ∣ = 30 となります。

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

足場 1 → 2 → 3 と移動すると、コストの総和は ∣ 10 − 20 ∣ + ∣ 20 − 10 ∣ = 20 となります。

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

足場 1 → 2 と移動すると、コストの総和は ∣ 10 − 10 ∣ = 0 となります。

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

足場 1 → 4 → 8 → 10 と移動すると、コストの総和は ∣ 40 − 70 ∣ + ∣ 70 − 70 ∣ + ∣ 70 − 60 ∣ = 40 となります。

カエルの段差移動（動的計画法④）

December 17, 2022

動的計画法

カエルが最小コストで段差を移動する問題を、動的計画法 を使って解いていきます。

[問題]

Ｎ個の足場があります。 足場には 1,2,…,N と番号が振られています。

各 i (1 ≦ i ≦  N) について、足場 i の高さは h_i です。

最初にカエルは、足場 1 にいます。

カエルは次の行動を何回か繰り返し、足場Nまで辿り着こうとしています。

足場 i にいるとき、足場 i + 1 または i + 2 へジャンプします。

このとき、ジャンプ先の足場を j とすると、コスト ∣h_i − h_j∣ (差分の絶対値)を支払う必要があります。

カエルが足場 N に辿り着くまでに支払うコストの 総和の最小値 を求めてください。

解法・ソースコード

メモ化テーブル memo[i] を頂点iへと至る最短経路を表していると定義します。

memo[i] の値を求めるために、次の２つを比較します。

頂点 i - 1まで最短経路で行ってから、頂点 i へと至る方法の最小コスト
memo[i - 1] + abs(h[i] - h[i - 1])
頂点 i - 2まで最短経路で行ってから、頂点 i へと至る方法の最小コスト
memo[i - 2] + abs(h[i] - h[i - 2])

memo[i] の値は、これらのうちの 最小値 となります。

以上を踏まえて実装すると以下のようなソースになります。

[Google Colaboratory]

#--------- 入力例1 ----------
lst = [10, 30, 40, 20]
#--------- 入力例2 ----------
# lst = [10, 10]
#--------- 入力例3 ----------
# lst = [30, 10, 60, 10, 60, 50]
#----------------------------
n = len(lst)    # 足場の数

memo = [float('inf')] * n
memo[0] = 0

for i in range(n):
    if i - 1 >= 0:
        memo[i] = min(memo[i], memo[i - 1] + abs(lst[i] - lst[i - 1]))
    if i - 2 >= 0:
        memo[i] = min(memo[i], memo[i - 2] + abs(lst[i] - lst[i - 2]))
print(memo[n - 1])

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

足場 1 → 2 → 4 と移動すると、コストの総和は ∣10 − 30∣ + ∣30 − 20∣ = 30 となります。

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

足場 1 → 2 と移動すると、コストの総和は ∣ 10 − 10 ∣ = 0 となります。

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

足場 1 → 3 → 5 → 6 と移動すると、コストの総和は ∣ 30 − 60 ∣ + ∣60 − 60 ∣ + ∣ 60 − 50 ∣ = 40 となります。

最長共通部分列（動的計画法③）

December 16, 2022

最長共通部分列

部分列 は系列のいくつかの要素を取り出してできた系列のことです。

二つの系列の共通の部分列を 共通部分列 と言います。

共通部分列のうちもっとも長いものを 最長共通部分列 と言います。

最長共通部分列 を求める問題を 動的計画法 を使って解いていきます。

問題

２つの文字列があります。

これら２つの共通部分列の長さの最大値を求めて下さい。

解法・ソースコード

メモ化テーブル を次のように定義します。

memo[i][j] は、【１つめの文字列のｉ文字まで】と【２つめの文字列のｊ文字まで】の

最長共通部分列の長さ

この定義を踏まえて、漸化式 を作成し 動的計画法（メモ化テーブル） を実装すると次のようになります。

[Google Colaboratory]

#---------- 入力例 ----------
a = 'ABCBDAB'
b = 'BDCABA'
#----------------------------
# メモ化テーブル
memo = {}

for i, a1 in enumerate(a):
    for j, b1 in enumerate(b):
        if a1 == b1:    # 文字が一致した場合
            # 最長共通部分列の長さを１つ増やす
            memo[i + 1, j + 1] = memo.get((i, j), 0) + 1
        else:           # 文字が一致しない場合
            # これまでの最長共通部分列で長いほうを選択
            memo[i + 1, j + 1] = max(memo.get((i, j + 1), 0), memo.get((i + 1, j), 0))

print('解：', memo[(len(a), len(b))])

[実行結果]

解： 4

解は 4 となりました。

２つの文字列を確認すると 最長共通部分列 が B, C, B, A となっていて解が正しいことが分かります。

ナップサック問題（動的計画法②）

December 15, 2022

動的計画法（順方向）

前回は 動的計画法 を使ってナップサック問題を解きましたが、再帰関数に合わせてループの順番が 逆方向 になっていました。

今回は、このループの順番を 順方向 に変えてみます。

[ナップサック問題]

Ｎ個の品物があります。

それぞれの品物の 重さ(weight) と 価値(value) は分かっています。

これらの品物からいくつか選んでナップサックに詰めていきます。

ナップサックにい列品物の総和は capacity を超えてはいけません。

選んだ品物の価値の総和として考えられる最大値を求めて下さい。

解法・ソースコード

ループを 順方向 に変えるためには、ループ文 と 漸化式 を少し変更する必要がありますが、根本的な内容は前回記事の処理と変わりません。

[Google Colaboratory]

#---------- 入力例 ----------
items = [{'weight':2, 'value':3},
         {'weight':1, 'value':2},
         {'weight':3, 'value':4},
         {'weight':2, 'value':2}]
capacity = 5
#----------------------------
# 動的配列
dp = {}
for i in range(0, len(items) ):             # アイテムを順方向にループ
    for j in range(capacity + 1):           # 重さを順番にループ
        if j < items[i]['weight']:          # 重さが許容範囲外の場合
            dp[i + 1, j] = dp.get((i, j), 0)
        else:                               # 重さが許容範囲内の場合
            # 品物を入れない場合
            a = dp.get((i, j), 0)
            # 品物を入れる場合（許容範囲の重さを減らし、価値を増やす）
            b = dp.get((i, j - items[i]['weight']), 0) + items[i]['value']
            dp[i + 1, j] = max(a, b)        # 価値が高いほうを選択

print('解：', dp[len(items), 5])

ループを 順方向 に変えることで、ループ文 や 漸化式 がシンプルで分かりやすくなったのではないでしょうか。

[実行結果]

解： 7

解（価値の総和の最大値）はこれまで同様 7 となっています。

ナップサック問題（動的計画法）

December 14, 2022

動的計画法

今回は 動的計画法 を使ってナップサック問題を解いていきます。

動的計画法 は、値を覚えて再利用する手法です。

[問題]

Ｎ個の品物があります。

それぞれの品物の 重さ(weight) と 価値(value) は分かっています。

これらの品物からいくつか選んでナップサックに詰めていきます。

ナップサックにい列品物の総和は capacity を超えてはいけません。

選んだ品物の価値の総和として考えられる最大値を求めて下さい。

前回使った メモ化した辞書型データ に注目してみます。

メモ化した辞書型データ は、ｉ番目以降の品物から、重さの総和がｊ以下 となるように選んだ時の 価値の総和の最大値 となっています。

再帰関数を書かなくても、直接この 漸化式 を用いて各項目の値を順に計算していくことにより、単純な二重ループ でナップサック問題を解くことができます。

（漸化式 とは、数列の各項をその前の頃から1通りに定める規則を表す等式のことです。）

解法・ソースコード

前回の 再帰関数 をもとに、動的計画法 で実装を行うと下記のようになります。

２重ループの中で、漸化式 を使って順番に メモ化テーブル に結果を格納していきます。

[Google Colaboratory]

#---------- 入力例 ----------
items = [{'weight':2, 'value':3},
         {'weight':1, 'value':2},
         {'weight':3, 'value':4},
         {'weight':2, 'value':2}]
capacity = 5
#----------------------------
# メモ化テーブル
dp = {}
for i in range(len(items) - 1, -1, -1):     # アイテムを後ろからループ
    for j in range(capacity + 1):
        if j < items[i]['weight']:          # 重さが許容範囲外の場合
            dp[i, j] = dp.get((i + 1, j), 0)
        else:                               # 重さが許容範囲内の場合
            # 品物を入れない場合
            a = dp.get((i + 1, j), 0)
            # 品物を入れる場合（許容範囲の重さを減らし、価値を増やす）
            b = dp.get((i + 1, j - items[i]['weight']), 0) + items[i]['value']
            dp[i, j] = max(a, b)    # 価値が高いほうを選択

print('解：', dp[0, 5])

[実行結果]

解： 7

解（価値の総和の最大値）はこれまで同様 7 となりました。

ナップサック問題（メモ化）

December 13, 2022

前回と同じナップサック問題を より効率的に解く方法 を考えます。

[問題]

Ｎ個の品物があります。

それぞれの品物の 重さ(weight) と 価値(value) は分かっています。

これらの品物からいくつか選んでナップサックに詰めていきます。

ナップサックにい列品物の総和は capacity を超えてはいけません。

選んだ品物の価値の総和として考えられる最大値を求めて下さい。

メモ化

前回は、再帰関数 を使ってナップサック問題を解きましたが、再帰関数が 同じ引数で何度もコールされる ことがありました。

このままでは非効率なので、メモ化 という方法で効率的に処理を行ってみます。

メモ化 では、最初の計算時の結果を記憶しておくことで、同じ引数での二度目以降の計算を省略 します。

ソースコード

メモ化 のために、9行目、13～14行目、23行目を追加しています。

[Google Colaboratory]

#---------- 入力例 ----------
items = [{'weight':2, 'value':3},
         {'weight':1, 'value':2},
         {'weight':3, 'value':4},
         {'weight':2, 'value':2}]
capacity = 5
#----------------------------
# メモ化用変数
memo = {}

# i番目以降の品物の中から重さの総和がj以下となるように選ぶ
def rec(i, j):
    if (i, j) in memo:      # メモに結果があったら
        return memo[i, j]   # その結果を返す

    if i == len(items):     # 品物がもう残っていない場合
        res = 0
    elif j < items[i]['weight']:    # 品物が入らない場合
        res = rec(i + 1, j)
    else:
        # 品物を入れない場合と入れる場合で価値が大きいほうを選ぶ
        res = max(rec(i + 1, j), rec(i + 1, j - items[i]['weight']) + items[i]['value'])
    memo[i, j] = res        # 結果をメモ化
    return res

print(rec(0, capacity))

[実行結果]

解（価値の総和の最大値）は前回同様 7 となりました。

今回の入力例では、同じ引数で再帰関数がコールされる回数 が少ないので大幅な効率化はしていませんが、この改良により 解ける問題のサイズを大幅に増やす ことができたことになります。

functools

functools というPythonの標準モジュールを使うと デコレータ を設定するだけで 簡単にメモ化 することができます。（8行目、11行目）

[Google Colaboratory]

#---------- 入力例 ----------
items = [{'weight':2, 'value':3},
         {'weight':1, 'value':2},
         {'weight':3, 'value':4},
         {'weight':2, 'value':2}]
capacity = 5
#----------------------------
import functools

# i番目以降の品物の中から重さの総和がj以下となるように選ぶ
@functools.lru_cache(maxsize=None)
def rec(i, j):
    if i == len(items):  # 品物がもう残っていない場合
        res = 0
    elif j < items[i]['weight']:    # 品物が入らない場合
        res = rec(i + 1, j)
    else:
        # 品物を入れない場合と入れる場合で価値が大きいほうを選ぶ
        res = max(rec(i + 1, j), rec(i + 1, j - items[i]['weight']) + items[i]['value'])
    return res

print(rec(0, capacity))

[実行結果]

ナップサック問題（再帰関数）

December 12, 2022