競プロ初中級者100問

DPL1B 0-1ナップザック問題

この記事で使うアルゴリズム

動的計画法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

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

この問題は動的計画法を用いて解くことができます。

方針

dp[n][w]を考えます。このリストは重さの総和がw以下となるようにn番目までの品物を選んだ時の価値の最大値を表します。

コード

貰うDP

1
2
3
4
5
dp[n][w-wn] --┐
              |
    ：        ：
              |
dp[n][w] -----┴--> dp[n+1][w]

dp[n][w-wn]が配列外参照になるかの判定が必要です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
N, W = map(int, input().split())
vw = []
for n in range(N):
    v, w = map(int,input().split())
    vw.append((v,w))
dp = [[0]*(W+1) for _ in range(N+1)]
for n in range(N):
    vn ,wn = vw[n]
    for w in range(W+1):
        if w-wn >= 0:
            dp[n+1][w] = max(dp[n][w-wn] + vn, dp[n][w])
        else:
            dp[n+1][w] = dp[n][w]
print (dp[N][W])

配るDP

1
2
3
4
5
dp[n][w] ----->dp[n+1][w]
           |
           :       ：
           |
           └-->dp[n+1][w+wn]

DP配列を大きめに確保することで、配列外参照を気にする必要がありません。

1
2
3
4
5
6
7
8
9
10
11
12
13
Wmax = 1000
N, W = map(int, input().split())
vw = []
for n in range(N):
    v, w = map(int,input().split())
    vw.append((v,w))
dp = [[0]*(W+Wmax+1) for _ in range(N+1)]
for n in range(N):
    vn ,wn = vw[n]
    for w in range(W+1):
        dp[n+1][w] = max(dp[n+1][w],dp[n][w])        
        dp[n+1][w+wn] = dp[n][w] + vn
print (dp[N][W])

wを逆に回しても良いです。

1
2
3
4
5
6
7
8
9
10
11
12
13
Wmax = 1000
N, W = map(int, input().split())
vw = []
for n in range(N):
    v, w = map(int,input().split())
    vw.append((v,w))
dp = [[0]*(W+Wmax+1) for _ in range(N+1)]
for n in range(N):
    vn ,wn = vw[n]
    for w in range(W+1)[::-1]:
        dp[n+1][w] = dp[n][w]    
        dp[n+1][w+wn] = max(dp[n][w] + vn,dp[n+1][w+wn])
print (dp[N][W])

記事情報

  • 投稿日：2020年5月13日
  • 最終更新日：2020年5月13日