[12865] 평범한 배낭

1차원 DP 배열의 변화 원리

1. 핵심 규칙: 뒤에서부터 채우기

1차원 배열을 앞에서부터 채우면, 방금 업데이트한 값을 같은 물건에서 또 참조하게 되어 '물건 중복 담기' 오류가 발생함. 하지만 뒤에서부터 채우면 dp[j-w]는 아직 '이전 물건까지만 계산된 값'을 유지하고 있으므로 2차원 배열의 dp[i-1][j-w]와 똑같은 효과를 냄.

2. 예시 상황 재현

• 배낭 용량: 7
• 물건 A: 무게 4, 가치 8
• 물건 B: 무게 3, 가치 6

[Step 1] 물건 A (4, 8) 처리

• j를 7부터 4까지 줄이며 계산함.
• dp[7] = max(0, dp[7-4]+8) = 8
• dp[6] = max(0, dp[6-4]+8) = 8
• dp[5] = max(0, dp[5-4]+8) = 8
• dp[4] = max(0, dp[4-4]+8) = 8
• 결과: [0, 0, 0, 0, 8, 8, 8, 8]

[Step 2] 물건 B (3, 6) 처리

• j를 7부터 3까지 줄이며 계산함.
• dp[7]: 기존 값 8 vs dp[7-3](4 용량의 값 8) + 6 = 14 (갱신)
• dp[6]: 기존 값 8 vs dp[6-3](3 용량의 값 0) + 6 = 8 (유지)
• dp[5]: 기존 값 8 vs dp[5-3](2 용량의 값 0) + 6 = 8 (유지)
• dp[4]: 기존 값 8 vs dp[4-3](1 용량의 값 0) + 6 = 8 (유지)
• dp[3]: 기존 값 0 vs dp[3-3](0 용량의 값 0) + 6 = 6 (갱신)
• 결과: [0, 0, 0, 6, 8, 8, 8, 14]

import sys

input = sys.stdin.readline

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

dp = [0 for _ in range(limit + 1)]

for i in range(n):
    w, v = map(int, input().strip().split())
    for j in range(limit, w - 1, -1):
        dp[j] = max(dp[j], v + dp[j - w])

print(dp[limit])