初中級者が解くべき過去問精選 100 問茶コーダーが解いてみた #8 ( 動的計画法：ナップザック DP 編 )

n = int(input())
dp = [0] * (n + 1)
(dp[0], dp[1]) = (1, 1)
def fibonacci(x):
    for i in range(2, x + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[x]

print(fibonacci(n))

35. 0-1 Knapsack Problem

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=ja

これがいわゆるナップザックDPと呼ばれる問題のようです。
最初にナップザックDPと聞いた際は、なんのことかわかりませんでした。
ナップザックの中にどれくらい詰めるかと言うことからこの名前がついているんですかね
（根拠はないです。）

先ほどのフィボナッチ数列の問題のように１次元のDPでは重さの制限をつけることが難しいので、２次元配列で解くことが出来ます。

ここら辺からもうわかんないです。

n, w = map(int, input().split())
v = [0] * n # 品物の価値
t = [0] * n # 重さ
for i in range(n):
    v[i], t[i] = map(int, input().split())
dp = [[0] * (w + 1) for _ in range(n + 1)] # （価値 * 重さ）
for i in range(n):
    for j in range(w + 1):
        if j < t[i]: # 追加できないとき
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - t[i]] + v[i])
print(dp[n][w])

36. Knapsack Problem

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C&lang=ja

先ほどの問題とめっちゃ似ていますね。
何が違うのか気づくのに１０分くらいかかってしましました。今回の問題は同じ品物をいくつでも入れることができるらしいですね。

なので、解法としては先ほどの問題のdpの遷移の条件に加えて

dp[i + 1][j - w[i]]

と言ったような条件式を加えてあげるとAC出来ます!!
（詳細は日本語が下手でできないので省略...）

n, W = map(int,input().split())
v = [0] * n # 価値
w = [0] * n # 重さ
for i in range(n):
    v[i], w[i] = map(int,input().split())
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(W + 1):
        if j < w[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i], dp[i][j - w[i]] + v[i])
print(dp[n][W])

37. Coin Changing Problem

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_A&lang=ja

今度はコインの問題ですね。
dp[j] と言うのを j 円を作るのに必要な最小のコイン枚数と定義してあげることで１次元のDPとして扱えます。

なんかよくわかんないけど難しいのには変わりないよね...
DPはとりあえずどう定義してあげるかが重要だなと感じました。

n, m = map(int,input().split())
c = list(map(int,input().split()))
dp = [10 ** 18] * (n + 1)
dp[0] = 0
for i in range(m):
    for j in range(n + 1):
        if j >= c[i]:
            dp[j] = min(dp[j], dp[j - c[i]] + 1)
print(dp[n])

38. Longest Common Subsequence

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C&lang=ja

俗に言う LCS(Longest Common Subsequence) の問題です。
TLなどではよくワードを見かけていましたが、意味を知らなかったので理解できてとても嬉しいです！
感想としては、「結構考える上に実装が重い！！」
と言った感じでした。
なのでライブラリとして保存している方もよく見かけるので自分も近いうちにやっておきたいです。

解法としては、

dp[i][j] := sのi番目、tのj番目までで作れる最大共通部分列文字列

と定義してあげて、DPの遷移を考えていきます。
方針は立ちましたが、上位勢の方にアドバイスをいただきながら、ACしました。
典型問題のようなので、近いうちにもう一度解き直しておきたい所です。

import sys
input = sys.stdin.readline
q = int(input().rstrip())
for i in range(q):
    s = input().rstrip()
    t = input().rstrip()
    # dp[i][j] := sのi番目、tのj番目までで作れる最大共通部分列文字列
    dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = max(dp[i][j] + 1, dp[i + 1][j], dp[i][j + 1])
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
    print(dp[len(s)][len(t)])

最後に

DPを避け続けてしまったせいで、投稿がとても遅くなってしまいました。（１ヶ月以上空いた？）
今度の動的計画法：ナップザック DP の亜種編では投稿したいのは山々ですが、最後の2問がやばいらしい（緑や水の人が言ってるからそう言うことらしい）のでたぶん投稿自体は飛ばすことになると思います。

なので次回は動的計画法：区間 DP になると思います。（これもめっちゃ難しいらしい）
遅くなると思いますが、よろしくお願いします！！

誤字脱字や間違い等ありましたら、DM等よろしくお願いいたします。
ありがとうございました！

精選100問って何？

過去の記事についてはこちら！！

第１回：全列挙

第２回：工夫して通り数を減らす全列挙

第３回：ビット全探索

第４回：順列全探索

第５回：二分探索

第６回：深さ優先探索

第７回：幅優先探索

動的計画法：ナップザック DP

34. Fibonacci Number

35. 0-1 Knapsack Problem

36. Knapsack Problem

37. Coin Changing Problem

38. Longest Common Subsequence

最後に