문제
https://www.acmicpc.net/problem/12865
예제
코드
n, k = map(int, input().split()) # 물건개수, 가방 크기
dp = [[0]*(k+1) for _ in range(n+1)]
w_list = [0]
for i in range(1, n+1):
w, v = map(int, input().split())
dp[i][w] = v
w_list.append(w)
for i in range(1, n+1):
w = w_list[i]
v = dp[i][w]
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])설명
먼저 input을 받으면 dp에 받은 물건(i)과 해당되는 무게(w)에 가치(v)를 넣는다 => dp[i][w] = v
그다음부터는 가방의 사이즈(j)를 최대 사이즈인 k까지 늘려가면서 물건(i)를 넣어본다
이때 2가지 경우가 있다. 둘 중 작은 값을 고르면 된다.
1. 내 물건을 넣고 남은 무게에 다른 물건을 넣었을 때 가치가 최대인 경우 => dp[i][j] = v + dp[i-1][j-w]
2. 내 물건을 안 넣어야 최대가 되는 경우 => dp[i][j] = dp[i-1,j]
---
예시로 더 알아보자
item 1번의 (무게가 4, 가치가 8)이 들어왔으므로 현재 dp[1][4] = 8이 저장되어있다
가방사이즈가 6으로 늘면 dp[1][6]은 내 물건을 넣었을 때보다 dp[0][6]을 넣었을 때가 13의 값으로 더 크므로 item 0을 넣는게 더 가치있게 된다
----
item 2(무게3, 가치6) 가 추가되었을 때, dp[2]도 같은 방식으로 구해보면
가방사이즈가 3으로 늘었을 때 dp[2][3] = 6 이지만
가방사이즈가 4로 늘면 dp[1][4]가 8로 가치가 더 커서 item1을 넣는 것이 가치있게 된다
가방사이즈가 7로 늘면 dp[2][7] = dp[2][4]+6 이 더 커서 자기자신과 dp[2][4]를 넣는 것이 가치있게 된다.
