解説
2次元のDP を用いることで高速に求められます。
以下では猫缶を 番目から 番目と数えます(問題文の 番目の猫缶を 番目と呼びます)。
を「 番目から 番目までの猫缶からいくつか選び、価格の合計がちょうど 円になるときの、大きさの合計の最大値」とします。そのような選び方がないときは とします。
初期化
番目の猫缶を買わない場合と買う場合を入れます。
ただし のときは買えないので、 は入れません。それ以外は とします。
遷移
について、 が でなければ、次の 2 つの更新を行います。
番目の猫缶を買わない場合
番目の猫缶を買う場合( のときだけ)
が最終的な答えになります。
計算量は です。
M, N = map(int, input().split())
K = []
V = []
for i in range(N):
k, v = map(int, input().split())
K.append(k)
V.append(v)
NEG = float('-inf')
# dp[i][c] = 0 番目から i 番目までの猫缶から選び、価格の合計がちょうど c 円のときの大きさの合計の最大値
dp = [[NEG] * (M + 1) for _ in range(N)]
dp[0][0] = 0
if K[0] <= M:
dp[0][K[0]] = max(dp[0][K[0]], V[0])
for i in range(N - 1):
for c in range(M + 1):
if dp[i][c] == NEG:
continue
# 買わない場合
dp[i + 1][c] = max(dp[i + 1][c], dp[i][c])
# 買う場合
if c + K[i + 1] <= M:
dp[i + 1][c + K[i + 1]] = max(dp[i + 1][c + K[i + 1]], dp[i][c] + V[i + 1])
print(max(dp[N - 1]))
ユーザー解説
ユーザー解説を書くユーザー解説はまだありません。