こんにちは、jjj0331です。今回は、Atcoderというプログラミング競技を通じて学んでいるアルゴリズムの中から、特に DP法（動的計画法） についてお話ししたいと思います。
DP法(動的計画法)とは？
DP法（Dynamic Programming）は、問題をいくつかの小さな部分に分けて、それぞれを解き、その結果を組み合わせて最終的な解を導き出す手法です。この方法は、特に次のような問題にとても役立ちます。
部分和問題: 集合の中から、特定の和を持つ部分集合を見つける問題。
ナップザック問題: 価値と重量が決まっている複数のアイテムの中から、できるだけ価値の高い組み合わせを選ぶ問題。
DP法の基本的な考え方
DP法の基本は、「大きな問題を小さく分けて解決する」ことにあります。まず大きな問題を、より小さな部分問題に分解します。そして、それらの解を再利用することで、効率よく最終的な答えを導き出します。
例えば、ナップザック問題では、各アイテムを「選ぶか、選ばないか」を順に決めていきます。こうすることで、最適な解を見つけ出せます。また、すでに計算した部分問題の結果をうまく活用することで、無駄な計算を省くことができます。
具体例：DP法の実際の適用例: ナップザック問題
DP法が効果を発揮する代表的な問題として、ナップザック問題があります。
例: ５kgまで入るカバンにアイテムを入れていきます。次のようなアイテムがあります：
パソコン: 重量 1kg, 価値 100
水: 重量 5kg, 価値 50
本: 重量 3kg, 価値 40
これらのアイテムを、合計10kgまで入るカバンに詰め込み、価値が最大になるようにします。
DP法を使った解法
この問題をDP法で解くために、重さの制限と各アイテムの価値を考慮しながら部分問題に分割して解いていきます。
DPテーブルの定義
dp[i][w] を、i 番目までのアイテムから重さ w までのカバンに詰めたときの最大価値とします。
漸化式
アイテム i を選ばない場合: dp[i][w] = dp[i-1][w]
アイテム i を選ぶ場合: dp[i][w] = dp[i-1][w - weight[i]] + value[i]
これにより、次のようにDPテーブルを更新していきます。
# アイテムのリスト: (重量, 価値)
items = [(1, 100), (5, 50), (3, 40)]
max_weight = 5
n = len(items)
# DPテーブルの初期化
dp = [[0] * (max_weight + 1) for _ in range(n + 1)]
# DPテーブルの更新
for i in range(1, n + 1):
weight, value = items[i - 1]
for w in range(max_weight + 1):
if w >= weight:
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight] + value)
else:
dp[i][w] = dp[i-1][w]
# 最終結果の出力
for row in dp:
print(row)
print(f"最大の価値: {dp[n][max_weight]}")
DPテーブルの視覚的表示
| アイテム\重量 | 0kg | 1kg | 2kg | 3kg | 4kg | 5kg |
|---|---|---|---|---|---|---|
| - | 0 | 0 | 0 | 0 | 0 | 0 |
| パソコン (1kg) | 0 | 100 | 100 | 100 | 100 | 100 |
| 水 (5kg) | 0 | 100 | 100 | 100 | 100 | 100 |
| 本 (3kg) | 0 | 100 | 100 | 100 | 140 | 140 |
結果の解釈
このプログラムを実行すると、最大の価値は140となります。これは、パソコン (1kg, 価値100) と 本 (3kg, 価値40) をカバンに入れることで達成されます。
DPテーブルの各行での動作
-
dp[0][w] (初期状態):
まだ何も選んでいない状態で、全ての重さに対して価値は 0 です。 -
dp[1][w] (アイテム: パソコン):
パソコンを選ぶか選ばないかを検討します。
w = 1kg 以上の重量では、パソコンを選ぶことができ、価値は 100 になります。 -
dp[2][w] (アイテム: 水):
水を選ぶか選ばないかを検討します。
w = 5kg の場合、パソコンを選んだ場合の価値 100 と、水だけを選んだ場合の価値 50 を比較します。100 の方が大きいため、DPテーブルは更新されません。 -
dp[3][w] (アイテム: 本):
本を選ぶか選ばないかを検討します。
w = 3kg 以上の場合、本を選ぶと、残りの容量にパソコンが入れられるので、パソコンと本を両方選んだ場合の価値は 100 + 40 = 140 になります。
最終的に、5kgの重さでは、同様に本とパソコンを選んだ場合が最適で、価値 140 が最大です。
まとめ
このように、DP法を用いることで、各ステップでどのアイテムを選ぶべきかを効率的に判断し、カバンに入れる最適な組み合わせを見つけることができます。最終的に、パソコンと本を選ぶことで、価値の合計を最大の 140 にすることができました。
A,B,C問題を解くのであればDP法を使用することはないのですが、
学習したので記事にしました。