[BOJ]12865普通リュック

5453 ワード
テキストリンク

[問題リンク]


https://www.acmicpc.net/problem/12865

[回答]


これは動的計画法で解決する必要がある問題である.
各重量に担持できる最大価値をdpアレイに格納して解いた.
具体的には、新しい重量/価値が偶発的に添加されると、dpアレイにすでに存在する値を用いて新しい可能な重量を作成することができ、対応する重量値が以前に存在した重量/価値より高い場合、新しい値をdpで格納する方法で作成することができる.
dpはいつも難しい...

[正解コード]

import sys
from collections import deque

input = sys.stdin.readline

n, k = map(int, input().split())

wv_arr = [] #무게/가치 배열
for _ in range(n):
    wv_arr.append(list(map(int, input().split())))

dp = [0] * (k + 1)
for w, v in wv_arr:
    if w <= k:
        temp = deque()
        for i in range(1, k - w + 1):
            temp.append(max(dp[i + w], dp[i] + v))
        dp[w] = max(dp[w], v)
        for i in range(k - w):
            dp[i + w + 1] = temp.popleft()


print(max(dp))
centosシステム内ネットワークインストールgoogle Chrome
プロトタイプJavaScript { }