夏休み（動的計画法⑦）

問題

 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
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
32
#--------- 入力例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 の順に活動を行えば最大幸福になります。