[백준 12865] 평범한 배낭

0. 제목

• 백준 12865 평범한 배낭
• BOJ 12865 평범한 배낭
• 파이썬 12865 평범한 배낭
• Python 12865 평범한 배낭

---

1. 문제

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

---

2. 풀이

• dp[i][j] = 배낭에 넣은 물품의 무게 합이 j일 때 얻을 수 있는 최대 가치
• 각 물품의 번호 i에 따라서 dp[i][j]를 갱신한다.
• 1부터 k까지 증가하는 변수 j가 입력된 무게보다 작은 경우에는 전에 입력된 가치인 dp[i-1][j]를 그대로 가져온다.
• j가 입력된 무게보다 크거나 같은 경우에는 max(dp[i - 1][j], dp[i - 1][j - w] + v) 의 값이 dp[i][j]의 값이 된다.
• 이 문제에서는 (4, 8), (3, 6)일 때가 가치합의 최댓값인데, 세번째 물건인 (3,6)이 들어왔을 때 dp[3][7] = 14 로 갱신이 된다.
• 반복문을 마친 후 dp[n][k]이 가치합의 최댓값이 된다.

---

3. 코드

n, k = map(int, input().split())
dp = [[0] * (k + 1) for _ in range(n + 1)]
 
for i in range(1, n + 1):
    w, v = map(int, input().split())
    for j in range(1, k + 1):
        if j < w:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            
print(dp[n][k])