[백준 #12865 파이썬] 평범한 배낭

냅색 알고리즘의 가장 기본이 되는 문제다! 어렵게 느껴지는 유형 중 하나다. 이러한 문제를 푸는 방법에 있어 가장 중요하게 생각해야 하는 부분이 있다.

 

1. 변화를 감지하는 방법

2. 변화를 기록하는 방법

 

어찌보면 dp 와 맥락을 같이 하고 있다고 생각하면 된다.

 

생각

1. 순서에 상관 없이 최적의 값을 도출할 수 있어야 한다.(정렬을 사용하지 않는다.)

2. 제한 무게 내에서, 이전 결과의 최적 값과 현재 결과값 + 더할 무게의 가치 를 비교한다. (이해가 안된다면 아래에서 설명!)

 

사실 이전에 풀어봤던 내용이라 지금은 쉽게 방법을 떠올릴 수 있다.

하지만, 처음 봤을 때는 생소하고 전혀 방향을 잡지 못했기 때문에 기억해 두는 것이 좋을 듯 하다.

 

구현

1. DP테이블을 구체적으로 만든다.

일반적으로 생각할 수 있는 부분은 무게를 인덱스로(제한조건이 있기 때문에) 그리고 값에 가치를 두는 방식으로 구현을 할 것이다.

그리고 그 안에서 갱신하는 방법을 고안한다.이 문제의 풀이도 맥락이 같다!

하지만 이러한 과정들이 익숙하지 않다면, 2차원으로 표현해서 먼저 연습해보고 1차원으로 풀이하는 방법에 대해 생각해보자

그 과정을 구체적으로 표현한다!

 

간단히 DP테이블으르 보자

0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0

무게를 계산하는 편의를 위해 n+1까지의 크기로 테이블을 만든다.

 

2. 구체적으로 생각해보자

처음으로 무게 6 가치 13의 물건을 가방에 넣는다고 가정하면 다음과 같은 테이블이 된다.

 

0	0	0	0	0	0	13	13
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0

그리고 무게 4 가치 8의 물건을 가방에 넣어보자

0	0	0	0	0	0	13	13
0	0	0	0	8	8	max(8,13) = 13	max(8,13) =13
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0

여기서 한번 생각을 해볼 수 있다. 여기는 단순히 8과 13을 비교해서 더 큰 13을 넣은 것일까?

(1,6)을 살펴보면 

1. 무게가 6인 가치 13의 물건 (여유무게 없음)

2. 무게가 4인 가치 8의 물건 (여유무게 2)

무게 2에 있는 가치도 더하여 비교해본 것이다. 왜냐면 그게 여유공간을 모두 활용한 최적의 결과이니까

그래서 따져보면

max(8+0,13) = 13

(1,2)의 값이 더하여 비교해 나온 값이다.

 

이런식으로 다음 번 결과를 살펴보자

0	0	0	0	0	0	13	13
0	0	0	0	8	8	13	13
0	0	0	6	8	8	13	14
0	0	0	0	0	0	0	0

(2,7)의 결과를 보자

max(8+6,13) = 14라는 건 눈으로 풀어봐도 알 수 있는 결과다.그런데 어떻게 이게 나왔는 지를 이해하는 것이 중요하다.

(2,7)을 보자. 세번쨰 물건을 비교하고 있는 상황이다.

 

6의 가치를 가진 무게 3의 물건 (현재 물건의 가치)이 있고  이전의 최적 결과 13이 있다.

무게가 3인 물건은 여유 무게가 4가 있다. 우리는 이걸 최적으로 활용해 줘야 한다.

그러므로 무게 4에 있던 결과를 더해줄 수 있다.

그 결과 14와 13으로 비교하여 최적의 결과를 얻게 된 것이다.

 

다음 경우의 수는 생략하지만 마지막 결과값(3,7)은 14라는 것을 이제 쉽게 알 수 있을 것이다.

 

결과적으로 냅색 문제는

0. 모두 최적의 상태에서 비교

1. 더 최적의 값이 있으면 갱신

2. 그렇지 못하면 돌아가기

의 특성을 생각해 주는 것이 문제 풀이에 도움이 된다.

 

이렇게 생각했다면 아주 잘하고 있다!

하지만 구현은 참 어렵다 ㅎㅎ

 

2차원 풀이

N, K = map(int, input().split())
bag = [[0,0]]
dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]

for _ in range(N):
    bag.append(list(map(int, input().split())))

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

1차원 풀이

N, K = map(int, read().split())
dp = [0] * (K+1)

for _ in range(N):
    w, v = map(int, read().split())
    for j in range(K, w-1, -1):
        dp[j] = max(dp[j], dp[j-w] + v)
print(dp[-1])