ナップザック問題(dpの練習)
Qiitaに書いてもいいけれど、納得できていないので。
蟻本55p周辺のナップザック問題
atcoder agc044に挑戦して惨敗したので勉強。ただ、問題の方はさっぱり。
4 2 3 1 2 3 4 2 2 5
# -*- coding: utf-8 -*- N = int(input()) wv = [[int(_) for _ in input().split()] for i in range(N)] W = int(input()) def rec(n, w): ans = 0 if n == N: return 0 # n番目の品物を使えない場合 elif wv[n][0] > w: return rec(n + 1, w) else: ans = max( rec(n + 1, w), rec(n + 1, w - wv[n][0]) + wv[n][1] ) return ans def solve(): return rec(0, W) print(solve())
N = int(input()) wv = [[int(_) for _ in input().split()] for i in range(N)] W = int(input()) dp = [[0] * (W + 1) for j in range(N + 1)] for i in range(N - 1, -1, -1): for j in range(W + 1): if j < wv[i][0]: dp[i][j] = dp[i + 1][j] else: dp[i][j] = max( dp[i + 1][j], dp[i + 1][j - wv[i][0]] + wv[i][1]) print(dp[0][W])
