atcoder_E-Knapsack2を解いてみた

概要

AtCoderのDPまとめコンテストのE問題を解いてみました。
解説はこちらの記事が分かりやすいと思いますが、いざ自分で実装するとなると中々手が動かせない。。。
そこで、記事の解説を図（手書き(;'∀')）で書いてみました。

解の方針

以下のように定義して、dpを順に更新していく。
詳しくはこちらの記事がやはり分かりやすいのでおススメです。

• dp[ i ][ sum_v ] := i-1 番目までの品物から価値が sum_v 以上を達成するように選んだときの、重さの総和の最小値

イメージ図

さて、解の方針（概念）は分かってけど、いざ実装しようと思ったら手が止まる(;'∀')
そこで少しでも分かりやすくするため図に書いてみた。

コード

上の図を見ながらなんとか実装。。。

E-Knapsack2.py

#E問題
#https://atcoder.jp/contests/dp/tasks/dp_e
import numpy as np
N,W = map(int,input().split())
wvlist = [list(map(int,input().split())) for _ in range(N)]
INF = 10**15
ans = INF

#初期条件
dp = np.full((N+1,N*1000+1),INF)
dp[0][0] = 0

for i in range(N):
    #ここを普通の配列で2重ループで処理するとTLEになる。numpyの機能を使ってすばやく処理。
    dp[i+1][:wvlist[i][1]] = dp[i][:wvlist[i][1]]
    dp[i+1][wvlist[i][1]:] = np.minimum(dp[i][wvlist[i][1]:],dp[i][:-wvlist[i][1]]+wvlist[i][0])

for i in range(N*1000+1):
    if W >= dp[N][i]:
        ans = i

print(ans)

ちなみに、機能は満たしてるけど性能的にout(TLEになる)のがこちら
2重ループしてるとこが遅い。

E-Knapsack2(TLE).py

#あっているけど、実行時間超過
N,W = map(int,input().split())
#N,W = [3,8]
wvlist = [list(map(int,input().split())) for _ in range(N)]
INF = 10**15
ans = INF
#初期条件
dp = [[INF for _ in range(N*1000+1)] for i in range(N+1)]
#dp = np.full((N+1,N*1000+1),INF)
dp[0][0] = 0

for i in range(N):
    for v in range(N*1000+1):
        if v-wvlist[i][1]>=0:
            dp[i+1][v] = min(dp[i+1][v],dp[i][v-wvlist[i][1]]+wvlist[i][0])
        dp[i+1][v] = min(dp[i+1][v],dp[i][v])

for i in range(N*1000+1):
    if W >= dp[N][i]:
        ans = i

print(ans)

以上です。
DPの問題を解くときは、2次元配列の操作が難しくて図を描かないと解けません💦
いつか頭の中でできるようになりたいですねー(´･ω･｀)