ナップザックDP - プログラミング初心者の日記

今回からAtCoderのD問題を解くためにアルゴリズムの勉強を始めます。

https://atcoder.jp/contests/abc032/tasks/abc032_d
上記の例でナップサックDPを使っていきます。
以下は上記の例の入力例1の場合で書いていきます。

N,W=map(int,input().split())
value=[]
weight=[]

for i in range(N):
    x,y=map(int,input().split())
    value.append(x)
    weight.append(y)
      
#DPテーブル      
dp=[[0]*(W+1) for i in range(N+1)]

for i in range(N):
    for j in range(W+1):
        #処理を書いていく

ここまでは大丈夫だと思います。
最初自分はDQテーブルがよくわからなかったので図を載せておきます。

f:id:nasubiFX:20201015000514p:plain — 入力例1の場合

こんな感じで横は重量の最大値、縦はi番目の荷物を取ります。

では、ループの処理を書いていきます

N,W=map(int,input().split())
value=[]
weight=[]

for i in range(N):
    x,y=map(int,input().split())
    value.append(x)
    weight.append(y)
            
dp=[[0]*(W+1) for i in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if j>=weight[i]:#荷物を選ぶ場合
            dp[i+1][j]=max(dp[i][j-weight[i]]+value[i],dp[i][j])
        else:#荷物を選ばないとき
            dp[i+1][j]=dp[i][j]
            
print(dp[N][W])