DA:dp

フィボナッチ数列

全探索

次のコードは，再帰関数を用いた全探索による解法です．ただし，fibonacci 関数の引数 n は正の整数であることを仮定しています．

def fibonacci(n):
    if n == 0 or n == 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(10))

しかしこれは無駄が多い実装です．fobonacci(n) を実行する際に，fibonacci(n-1) と fibonacci(n-2) が実行されますが，fibonacci(n-1) の中でも fibonacci(n-2) がまた実行されることになります．よって，このままでは全く同じ計算を何回も繰り返すことになります．

全探索（既に計算したものをメモしておく戦略）

これを，既に計算したものは結果を保存して使い回す，という戦略で計算してみましょう．ここでは，n=10ならば，長さ10のリストを準備して，その k 番目の要素に fibonacci(k+1) が格納されるようにします．この戦略を実装したものが，次のコードです．（ただし， n=1 の場合に，リスト memo の長さは 1 なので， "memo[1] = 1" のところでエラーが出てしまう．これを避けるため，memo の長さを n+1 としてあります．）

def fibonacci(n):
    if memo[n] != 0:
        return memo[n]
    a = fibonacci(n-1) + fibonacci(n-2)
    memo[n] = a
    return a

n = 10

memo = [0 for i in range(n+1)]
memo[0] = 1
memo[1] = 1

print(fibonacci(n))

動的計画法

フィボナッチ数列の場合，普通に小さい方から順に計算していくのが動的計画法になっていいます．長さ n のリスト memo を準備して，0 番目から順に埋めていけば良い，ということになります．（ただし， n=1 の場合に，リスト memo の長さは 1 なので， "memo[1] = 1" のところでエラーが出てしまう．これを避けるため，memo の長さを n+1 としました．）

def fibonacci_dp(n):
    memo = [0 for i in range(n+1)]
    memo[0] = 1
    memo[1] = 1
    for i in range(2,n+1):
        memo[i] = memo[i-1] + memo[i-2]
    return memo[n-1]

print(fibonacci_dp(10))

Frog 1

再帰関数で解く方法

def solve(n):
    if n == 0:
        return 0
    if n == 1:
        return abs(h[1] - h[0])

    a = #ここを埋めてください
    b = #ここを埋めてください

    return min(a, b)

N = 7
h = [2, 9, 4, 5, 1, 6, 10]
print(solve(N-1))

結果をメモしつつ再帰関数で解くパターン

def solve(n):
    if n == 0:
        return 0

    #ここを埋めてください（すでにメモしている場合はその値をreturnする）

    a = #ここを埋めてください
    b = #ここを埋めてください
    c = min(a, b)
    memo[n] = c

    return c

N = 7
h = [2, 9, 4, 5, 1, 6, 10]
memo = [0 for i in range(N)]
memo[1] = #ここを埋めてください
print(solve(N-1))

動的計画法で解くパターン

def dp():
    memo = [0 for i in range(N)]
    memo[1] = #ここを埋めてください

    for i in range(2, N):
        memo[i] = #ここを埋めてください
    return(memo[-1])

N = 7
h = [2, 9, 4, 5, 1, 6, 10]
print(dp())

ナップサック問題

動的計画法による解法

ただし，一部未完成です．完成させてください．

def dp(products, W):
    N = len(products)
    memo = [[0 for i in range(W+1)] for i in range(N+1)]

    for i in range(1, N+1):
        for s in range(1, W+1):

            w = products[i-1][0]
            v = products[i-1][1]

            ########## 未完成 ここから ##########
            # a = i-1番目の品物を選ぶ場合の価値の総和（sの値によって場合分けが必要）
            # b = i-1番目の品物を選ばなかった場合の価値の総和
            ########## 未完成 ここまで ##########

            memo[i][s] = max(a, b)

    return(memo[-1][-1])

products = ((2,3), (1,2), (3,6), (2,1))
for W in range(1, 11):
    print('W: %i\t%.01f' % (W, dp(products, W)))

部分和問題

基本的な部分和問題

N 個の正の整数からいくつかを選んで，それらの和を W にすることができるか，を判定せよ．

部分和問題を動的計画法で解く，未完成のプログラムです．完成させてください．

def dp(numbers, W):
    N = len(numbers)
    memo = [[0 for i in range(W+1)] for i in range(N+1)]

    for i in range(1, N+1):
        for s in range(1, W+1):

            ####### 未完成 ここから #######
            w = 
            v = 
            if :
                a = 
            else:
                a = 
            b = 
            ####### 未完成 ここまで #######

            memo[i][s] = max(a, b)

    if memo[-1][-1] == W:
        return 'Yes'
    else:
        return 'No'

numbers = [4, 5, 7, 11, 13, 16]
for W in range(1, 21):
    print('W: %i\t%s' % (W, dp(numbers, W)))

ちょっと捻った部分和問題

N 個の正の整数からいくつかを選ぶところは同じであるが，選んだ整数を k 倍（k は正の整数）してから足しても良い，とする．この条件で，総和を W にすることができるか，を判定せよ．

基本形の部分和問題のプログラムを修正して，作成してください．