1. 문제

---

출처: 백준 12865번 평범한 배낭

2. 풀이

---

이 문제는 2차원 DP 표를 만들어서 풀이하면 된다.

먼저, 집어넣는 물건의 개수와 최대 가방 무게를 이용하여 2차원 DP 리스트를 만든다.

DP 표를 채워나갈 때, 지금 번호의 물건을 넣을 수 없다면 이전의 DP 값을 가져오면 된다. 이전의 DP 값이 이전의 물건들을 넣었을 때 가장 큰 값이기 때문이다.
만약, 지금 번호의 물건을 새롭게 넣을 수 있는 무게가 된다면, 비교를 해야 한다.

1. 이전의 DP 값
2. 지금 물건 가치 + 지금 물건의 무게를 제외하여 집어넣었을 때 DP 값

2번이 더 크다면 2번으로 DP 값을 집어넣으면 되고, 1번이 더 크다면 이전에 채운 방식과 똑같이 채우면 된다.

모든 조합을 살펴 본 경우인 표의 가장 하단 오른쪽 부분의 값을 결과로 출력하면 된다.

3. 소스코드

---

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

things = [list(map(int,input().split())) for _ in range(n)]
dp = [[0]*(w+1) for _ in range(n)]

for i in range(n):
    for j in range(1,w+1):
        weight = things[i][0]
        if j < weight:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j-weight]+things[i][1],dp[i-1][j])
print(dp[n-1][w])    

4. 그 외

---

길었던 동적계획법 1 단계가 끝났다. 문제를 잘 정의하는 것이 DP의 핵심임을 배울 수 있는 단계였다.