【超基本】初心者に贈るアルゴリズム論　～動的計画法～

はじめに
動的計画法
ナップサック問題
例題
考え方
実装例
おわりに
参考

はじめに

こんにちは．talosです．

今回はナップサック問題を例題に，動的計画法を説明します．

競技プログラミングとかでもよく使われるので，これから挑戦しようという人は必見です．

動的計画法

動的計画法（DP：Dynamic Programming）は問題を部分問題に分割し，それらを解くことで最終的な解を求める方法です．

似たような方法に分割統治法がありますが，これとの違いは部分問題を解いた結果を保存しておくことです．

これによって，分割統治法でよくある同じ部分問題を何度も解いてしまうということを避けることができます．

言葉だけではわかりにくいと思うので，ナップサック問題を例に見てみましょう．

ナップサック問題

ナップサック問題は，ナップサックにどの荷物を入れるか考える問題です．

しかし，なんでも詰めればよいというものではありません．

ナップサックには限界があり，重量制限を超えて荷物を入れることができません．

さらに，荷物にはそれぞれ価値があり，ナップサック内の荷物の価値の合計をできるだけ高くしたいと考えています．

すべての組み合わせを計算するにはとても時間がかかります．

効率よく計算するにはどうしたらよいでしょうか？

例題

今日，ふとし君は遠足に行きます．

遠足と言えばお弁当です．

家にはA～Eの5つのお弁当があります．

食いしん坊のふとし君は全部持っていこうとしました．

しかし，ふとし君はあることに気づきました．

全部をナップサックに入れるとナップサックが持ち上がりません．

どうやらふとし君が持ち上げることができる重量は10kgまでのようです．

ふとし君がなるべく多くのカロリーを摂取するためにはどのお弁当の組み合わせがよいでしょうか．

ただし，ナップサックの重量は考えないものとします．

f:id:talosta:20190723201941p:plain

考え方

まず，Aだけについて考えてみましょう．

f:id:talosta:20190723205559p:plain

当然入りますね．

解の一つとしてテーブルに保存しておきます．

次に，AとBについて考えてみます．

Bだけ入れようとするともちろん入ります．

f:id:talosta:20190723210850p:plain

さらに，Aが入っているところにBを入れることもできます．

f:id:talosta:20190723210935p:plain

A，B，Cについても同様に，Cだけ入れることもできますし，Aだけが入っているところやBだけが入っているところ，さらにAとBが入っているところに入れることもできます．

f:id:talosta:20190723220618p:plain

では，A，B，C，Dについて考えてみましょう．

いつものごとく，Dだけを入れることはできます．

さて，上のテーブルを見ると，上から4つ目まではDを入れることができますが，下の3つはDを入れると重量オーバーしてしまいます．

したがって，テーブルはこのように更新されます．

f:id:talosta:20190723221230p:plain

ちょっと待ってください．

実はこのテーブルは無駄があります．

(A，B)と(D)，(B，C)と(A，D)，(A,B,C)と(C,D)はそれぞれ総重量も総カロリーも同じです．

(D)と(A,D)，(C,D)はいらないので省いちゃいましょう．

するとこのようになります．

f:id:talosta:20190723222451p:plain

最後に，すべてのお弁当について考えます．

こちらも，Eだけ入れることはできます．

また，Aだけ，Bだけ，Cだけのナップサックにいれることもできます．

しかし，(E)と(B,E)についてはすでに同重量でより多くのカロリーを摂取できる組み合わせがあるので省きます．

よって，テーブルはこのようになります．

f:id:talosta:20190723222914p:plain

一番下の(C,E)の組み合わせが最も多くのカロリーを摂取できることがわかりました．

こうして，ふとし君はCとEのお弁当を持って遠足に向かったのでした．

f:id:talosta:20190723223328p:plain

実装例

MAX = 10  # ふとし君が持ち上げられる重量の上限
w = [2, 3, 4, 5, 6]   # 重量
cal = [400, 500, 800, 900, 1100]  # カロリー
name = 'ABCDE'

def knapsack(lim):    
    table = [[0, 0, []]]  # 解：総重量，総カロリー，お弁当
    w_max = 0             # 総重量の最大値
    cal_max = 0           # 総カロリーの最大値
    b_max = []            # 総カロリー最大のときのお弁当

    for i in range(len(name)):
        
        # 既出の解ansに荷物iを加える
        for ans in table:
            
            # 重量オーバーしてない and お弁当iがナップサックに入っていない
            if ans[0] + w[i] <= lim and name[i] not in ans[2]:
                if check(table, ans, i) == True:
                    w_temp = ans[0] + w[i]
                    cal_temp = ans[1] + cal[i]
                    b_temp = ans[2] + [name[i]]
                    
                    # テーブルに保存
                    table.append([w_temp, cal_temp, b_temp])

                    print('総重量=' + str(w_temp) + 'kg'
                         + ' 総カロリー=' + str(cal_temp) + 'kcal'
                         + ' お弁当=' + str(b_temp))
                    
                    # 最大カロリーのときの総重量，総カロリー，お弁当を更新
                    if cal_temp > cal_max:
                        w_max = w_temp
                        cal_max = cal_temp
                        b_max = b_temp
                        
    print('\n最適解:総重量=' + str(w_max) + 'kg'
          + ' 総カロリー=' + str(cal_max) + 'kcal'
          + ' お弁当=' + str(b_max))

# 同重量で総カロリーが同等以上のものがないか確認
def check(table,ans, i):
    for a in table:
        if a[0] == ans[0] + w[i] and a[1] >= ans[1] + cal[i]:
            # ある
            return False
    
    # ない
    return True

knapsack(MAX)

総重量=2kg 総カロリー=400kcal お弁当=['A']
総重量=3kg 総カロリー=500kcal お弁当=['B']
総重量=5kg 総カロリー=900kcal お弁当=['A', 'B']
総重量=4kg 総カロリー=800kcal お弁当=['C']
総重量=6kg 総カロリー=1200kcal お弁当=['A', 'C']
総重量=7kg 総カロリー=1300kcal お弁当=['B', 'C']
総重量=9kg 総カロリー=1700kcal お弁当=['A', 'B', 'C']
総重量=8kg 総カロリー=1400kcal お弁当=['B', 'D']
総重量=10kg 総カロリー=1800kcal お弁当=['A', 'B', 'D']
総重量=8kg 総カロリー=1500kcal お弁当=['A', 'E']
総重量=10kg 総カロリー=1900kcal お弁当=['C', 'E']

最適解:総重量=10kg 総カロリー=1900kcal お弁当=['C', 'E']