[백준/Python] - 12865 평범한 배낭

https://www.acmicpc.net/problem/12865

제출코드

N, K = map(int, input().split())
arr = [[0,0]]
for _ in range(N):
    arr.append(list(map(int ,input().split())))
dp = [[0] * (K+1) for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(1,K+1):
        if j < arr[i][0]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-arr[i][0]] + arr[i][1])

 

베낭 문제 DP조건

1. 최적 부문 구조: 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결 할 수 있다.

2. 중복 부분 문제: 동일한 작은 문제를 반복적으로 해결한다.

 

배낭의 부분 문제를 적용하기 위해서 물건을 하나씩 고려하되 배낭 용량에 따른 최대 가치를 저장해나가는 방식으로 찾는다.

 

일단 핵심 조건을 줘야한다.

1. 현재 배낭의 허용용량 j가 i번째 물건의 무게 보다 작을 때

2. 현재 배낭의 허용량 j가 i번째 물건의 무게보다 크거나 같을 때

 

위 그림과 같은 느낌으로 가도된다.

 

그래도 이해가 안된다면?

        if j < arr[i][0]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-arr[i][0]] + arr[i][1])

이 점화식이 직관적으로 와닿지 않을 수 있다.

 

DP에서 문제를 풀 때 점화식을 도출하는 일반적인 접근 방법은

마지막 단계에서의 선택 을 고려하는 것이다.

 

배낭문제에서 dp[i][j]는 i번째 물건까지 고려했을 때

용량 j를 넘지 않으면서 얻을 수 있는 최대 가치이다.

 

i번째 물건에 대해 우리는 딱 2가지만 선택이 가능하다.

1. i번째 물건을 넣지 않는다.

2. i번째 물건을 넣는다.(넣을 수 있을 때만)

 

i번째 물건을 넣지 않을때

i번째 물건은 그냥 무시하는 것과 같다.

그래서 최대 가치는 i-1번째 물건들까지만 고려해서 용량을 채웠을 때 얻을 수 있는 최대 가치와 동일할 것이다.

 

위 테이블 표에서 마지막 무게가 5인 마지막 idx를 보자

배냥 용량이 3인 공간에 우리는 용량5인 값을 넣지 못한다.

그럼 i-1번째 물건들까지만 고려한 용량 j를 채웠을 때 최대가치는 

이미 DP테이블의 dp[i-1][j]에 계산되어 저장이 되어있다. 

 

i번째 물건을 배낭에 넣을 때

i번째 물건을 넣기로 결정을 했으면 이 물건이 배낭용량 j에 들어갈 수 있을지를 선택을 해야한다.

i번째 물건의 무게는 arr[i][0]일 것이다. --> arr[i][0]이 j보다 크면 이 선택지는 불가능하다.

 

i번째 물건을 배낭에 넣으면

배낭에 i번째 물건의 가치 arr[i][1]만큼 가치가 더해진다.

그럼 당연히 배낭의 남은 용량은 (배낭 용량 - 물건의 무게)-> (j-arr[i][0])이 된다.

i-1번째 물건까지 고려하고 남은 용량 j - arr[i][0]을 채웠을 때의 최대가치는

이미 DP테이블의 dp[i-1][j - arr[i][0]]에 계산되어 저장되어 있다.

 

여기서 핵심은 DP테이블에 i-1번째 행은 

i-1번째 물건까지 고려했을 때, 모든 가능한 용량에 대해 얻을 수 있는 최대 가치들을 저장하고 있는 행이다.

--> 현재 물건을 고려하기 전까지만 가지고 모든 용량에 대해 최적의 값을 구해놓은 상태이다.

 

---

그냥 개어렵다...