문제 출처 : https://www.acmicpc.net/problem/12865
문제 파악
- 물건 개수
N(1 ≤ N ≤ 100) - 각 물건:
- 무게
W[i](1 ≤ W[i] ≤ 100,000) - 가치
V[i](1 ≤ V[i] ≤ 1,000)
- 무게
- 배낭이 버틸 수 있는 최대 무게
K(1 ≤ K ≤ 100,000)
목표
배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구하는 0/1 배낭(knapsack) 문제.
처음 떠올렸던 잘못된 생각 정리
처음엔 이런 식으로 생각하기 쉽다.
dp[i] = i번째 물건까지 봤을 때 얻을 수 있는 최대 가치- i번째 물건을 넣을 수 있으면
dp[i] = dp[i-1] + V[i]? - 못 넣으면
dp[i] = dp[i-1]혹은dp[i-2] + V[i]… 중 최댓값?
이 생각의 치명적인 문제는 두 가지다.
1) 무게 K라는 정보가 상태에 없다
같은 i라 하더라도
- 현재까지 쓴 무게가 5일 때의 최대 가치
- 현재까지 쓴 무게가 50일 때의 최대 가치
는 완전히 다른 상황이다.
즉,
“몇 번째 물건까지 고려했는가(i)”만으로는 이 문제 상태를 표현할 수 없다.
현재까지 쓴 무게라는 정보(w)가 같이 필요하다.
2) “dp[i-2] + V[i] 중 최댓값”으로는 K를 넘는지 체크 불가능
dp[i-2] + V[i] 같은 식으로는
- 지금까지 총 무게가 얼마인지 알 수 없다.
- 따라서 K를 넘는지, 안 넘는지를 애초에 체크할 방법이 없다.
그래서 이 문제의 스킬은
dp를 2차원 배열로 정의해서
“몇 번째 물건까지 썼는지” + “현재 허용 무게”를 동시에 상태로 잡는 것
이다.
핵심 아이디어: 2차원 DP 정의
이 문제의 정석 정의:
dp[i][w] = 1번부터 i번 물건까지 고려했을 때, 허용 무게가 w일 때 얻을 수 있는 최대 가치
- i: 0 ~ N
- w: 0 ~ K
초기값은
- 아무 물건도 안 쓰면 가치 = 0
→dp[0][w] = 0(0 ≤ w ≤ K)
→dp[i][0] = 0(0 ≤ i ≤ N)
이렇게 정의하면
- “i번째 물건까지 봤을 때”
- “현재 배낭에 허용된 최대 무게가 w일 때”
라는 두 축을 모두 상태로 관리할 수 있다.
점화식: “넣을지 말지” 두 경우만 보면 된다
i번째 물건의
- 무게:
weight - 가치:
value
라고 하자.
w라는 허용 무게에 대해, 우리는 두 가지만 고려하면 된다.
1) i번째 물건을 안 넣는 경우
그냥 이전 상태 그대로 사용:
dp[i][w] = dp[i-1][w]2) i번째 물건을 넣는 경우
i번째 물건 무게 weight를 넣으면
허용 무게 w 중에서 weight만큼을 써 버리므로
이전 상태에서는 w - weight까지만 쓸 수 있었다.
그 상태에서 i번째 물건의 가치 value를 더해주면 된다.
dp[i][w] = dp[i-1][w - weight] + value단, 당연히 w >= weight여야 가능.
최종 점화식
if w < weight:
dp[i][w] = dp[i-1][w] # 넣을 수 없음 → 이전 값 그대로
else:
dp[i][w] = max(
dp[i-1][w], # i번째 물건 안 넣는 경우
dp[i-1][w - weight] + value # i번째 물건 넣는 경우
)여기서 한 번 짚고 넘어간 직관:
i-1까지는 dp[i-1][w]가 최고였는데,
i번째 물건을 넣으려면
앞에서 몇 개를 빼고 이거 하나만 넣는 게 더 클 수도 있는 거 아냐?
라는 의문을 정확히 저 점화식에서 처리해준다.
dp[i-1][w - weight] + value
→ i번째 물건을 넣기 위해
“앞에서 사용하던 조합 일부를 버린 상태(dp[i-1][w - weight])”에
i번째 물건을 추가해서 만든 새로운 조합
즉,
“앞에 네 개 빼고 이거 하나만 넣는 게 더 이득인 상황”이
바로 dp[i-1][w - weight] + value에서 모두 고려된다.
결론적으로,
dp[i][w]는 항상
“i번째 물건까지 고려했을 때 만들 수 있는 모든 합법적인 조합 중 최대 가치”를 유지하게 된다.
해답 코드
import sys
input = sys.stdin.readline
N, K = map(int,input().split())
# 예제 1 : K = 7 , 즉 7 까지 배낭에 담을 수 있음
dp = [[0]*(K+1) for _ in range(N+1)]
items = [[0,0]] # items[1]부터 실제 물건이 들어가도록 의도적으로 앞에 [0,0]을 넣은 것
for i in range(N):
W, V = map(int,input().split())
items.append((W,V))
for i in range(1, N+1):
for j in range(0, K+1):
weight = items[i][0]
value = items[i][1]
if j < weight:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight]+value)
print(dp[N][K])2차원 dp 더 연습해야하겠다.
