キン〇マハムスター佐藤  2021/04/27更新

D、D、D、DPちゃうわっ!(Python動的計画法)


 プログラミングの世界では有名な”ナップサック問題”というのがあります。「初めにいくつか荷物があり、ナップサックに最大で何個の荷物が入るか?」という問いです。これはDP(動的計画法)という方法で効率よく解けるのですがこれを理解して使いこなすのは難しく高い学習コストが掛かります。しかしながらプログラムで利用するだけならば、やり方を覚えておけばOK。完璧に理解したい人でも手を動かして使っているうちに段々と理解できるようになっていきます。まず暗記しましょう。DPが利用できると処理計算量が少ない、速いプログラムが書けるようになります。

最低でも下の2問を暗記してしまいましょう。

サンプル問題1

 重さと価値がそれぞれ、w_i,v_iであるようなN個の品物があります。これらの品物から、重さの総和がWを超えないように選んだ時の価値の総和の最大値を求めなさい。

入力 N=3, W=3, (w,v)={(2,3), (3,4), (1,2)}

N, W = map(int,input().split())
w = list(map(int,input().split()))
v = list(map(int,input().split()))

dp = [[0] * (W + 1) for _ in range(N + 1)]    # dpテーブル

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][j - w[i]] + v[i])
print(dp[N][W])




サンプル問題2

 x_iの数字が書かれたN枚のカードが与えられています。カードを組み合わせて数字の総和がMを超えない範囲の最大の数を答えなさい。

入力 N=4,M=999,x = [200, 25, 500, 62]


N,M = map(int,input().split())
x = [int(input()) for _ in range(N)]

dp= [[0 for j in range(M + 1)] for i in range(N)]
# 1番目のカード
for j in range(M + 1):
  if x[0] <= j:
    dp[0][j] = x[0] # 1番目のカードを追加

# 2番目以降のカード
for i in range(N):
  for j in range(M + 1):
    tmp_not_choice = dp[i-1][j]
    if x[i] > j: # コスト不足のとき
      dp[i][j] = tmp_not_choice 
    else:
      tmp_choice = dp[i-1][j - x[i]] + x[i]
      dp[i][j] = max(tmp_choice,tmp_not_choice)

print(dp[N - 1][M])



タイトルとURLをコピーしました