BC 032 D ナップサック問題 - いろんなことで四苦Hack（仮）

続きです。

ナップザックを条件的にやるやつだと思います。

まだTLEなので、途中経過だけ書いておこうかなって。

ぬっ。

from collections import defaultdict

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

for i in range(N):
    vv, ww = map(int, input().split())
    v.append(vv); w.append(ww)

if N <= 30:
    dp = defaultdict(lambda: defaultdict(lambda: None))

    def rec(pos, rest):
        if pos == N:
            return 0
        if not (dp[pos][rest] is None):
            return dp[pos][rest]
        ans = rec(pos+1, rest)
        if rest-w[pos] >= 0:
            ans = max(ans, rec(pos+1, rest-w[pos])+v[pos])
        dp[pos][rest] = ans
        return ans
    print(rec(0, W))
elif 1 <= w[0] <= 1000:
    dp = [[0 for j in range(W+1)] for i in range(N+1)]
    for i in range(N-1, -1, -1):
        for j in range(0, W+1):
            if j-w[i] >= 0:
                dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]]+v[i])
            else:
                dp[i][j] = dp[i+1][j]
    print(dp[0][W])
else:
    INF = 10**7
    V_MAX = 1000
    N_MAX = 200
    dp = [[10**7 for j in range(V_MAX*N)] for i in range(N+1)]
    dp[N][0] = 0
    for i in range(N-1, -1, -1):
        for j in range(0, V_MAX * N_MAX):
            if j-v[i] >= 0:
                dp[i][j] = min(dp[i+1][j], dp[i+1][j-v[i]]+w[i])
            else:
                dp[i][j] = dp[i+1][j]
    res = 0
    for i in range(V_MAX * N_MAX):
        if dp[0][i] <= W:
            res = i
    print(res)

今のうちに、C++に変えときたかったんだけど時間的に無理なんですよね。 c++ にしたらどう変わるのか。個人的に、メモ化、重さでDP、価値でDPだと怪しい感じがある。ちょっと楽しみですわね☝︎