[BOJ] 12865번 : 평범한 배낭(DP, Knapsack)

접근

문제 그대로 평범한 배낭 문제다. D.P.를 이용한 Knasack알고리즘을 사용해서 해결할 수 있다.

(여담이지만, 올리고 있는 글순서를 보면 알겠지만 솔브닥 클래스 클리어중인데, 이 문제 2년전쯤 그리디 공부할 때 시도했다가 틀리고 안풀고있었던걸 이제 알았다.)

(여담2이지만, 이번에 풀 때도 1초틀이었는데, 2년전에 시도했던 코드랑 구조가 똑같았다. 난 발전이 없는것인가...? 하지만 이번엔 해결했다. 내가 틀린 반례도 적어두겠다.)

 

해결

Knapsack 알고리즘을 사용하지 않고, 전체 탐색으로 해결 자체는 가능하다. 당연히 시간초과가 나겠지만.

그러니까 배낭문제는 그냥 배낭으로 풀자..

변수는 아래와 같다.

• $ N $ : 물건의 갯수
• $ K $ : 버틸 수 있는 최대 무게

dp Table은 $ (K+1, N+1) $ 의 차원으로 구성해준다. => 중요하다.

예제 입력인 $ N = 4, K = 7 $로 설명을 진행하겠다.

⬇️ k  \ n  ➡️	0 (무게, 가치)	1 (6, 13)	2 (4, 8)	3 (3, 6)	4 (5, 12)
0
1
2
3
4
5
6
7

행과 열을 한개씩 더 추가해준 이유는 0일 때의 상태도 중요하기 때문이다.

행을 $ K + 1 $로 둔 이유는, 버틸 수 있는 최대 무게가 늘어남에 따라 최대 가치를 저장하기 위함이다.

열을 $ N + 1 $로 둔 이유는, 해당하는 물건이 들어올 때 최대 가치를 저장하기 위함이다.

결론적으로는 $ dp[k][n] $ 는 최대 수용가능 무게가 $ k $일 때, $ n $번째 물건까지 순회했을 때의 최대 가치의 값을 갖는다고 이해할 수 있다.

그럼 이제 순회를 진행해보자.

위의 이해를 바탕으로 $ k = 0 $ 또는 $ n = 0 $일 때는 저장할 수 있는 최대 무게가 0, 아무 물건도 없을 때라는 의미니까 해당하는 값들은 모두 저장 최대 가치가 0일 것이다. 테이블을 업데이트 해주자!

⬇️ k  \  n  ➡️	0 (무게, 가치)	1 (6, 13)	2 (4, 8)	3 (3, 6)	4 (5, 12)
0	0	0	0	0	0
1	0
2	0
3	0
4	0
5	0
6	0
7	0

 

사실 실제로는 이렇게 업데이트 되지 않고, 행 -> 각각의 열로 업데이트 되기에 이해를 돕기 위해서 미리 다 적어둔다.

그러면 순회 순서를 맞춰서 생각해보자.

$ k = 0 $ 일 때는 모두 0으로 초기화 됐을 것이니, 이번 순회는 $ k = 1 $ 일 때일 것이다.

$ k = 1 $의 의미는 최대 수용 가능 무게가 1 이라는 것이다. 그러면 물건들을 순회해보자.

⬇️ k  \  n  ➡️	0 (무게, 가치)	1 (6, 13)	2 (4, 8)	3 (3, 6)	4 (5, 12)
0	0	0	0	0	0
1	0	1<6 => 0	1<4 => 0	1<3 => 0	1<5 => 0
2	0
3	0
4	0
5	0
6	0
7	0

 

셀에 써놓은 것처럼, 최대 수용 무게 1에서는 수용할 수 있는 물건이 없기에 최대 가치가 모두 0이 된다.

그 다음 순회 $ k = 2 $로 넘어가보자.

⬇️ k  \  n  ➡️	0 (무게, 가치)	1 (6, 13)	2 (4, 8)	3 (3, 6)	4 (5, 12)
0	0	0	0	0	0
1	0	0	0	0	0
2	0	2<6 => 0	2<4 => 0	2<3 => 0	2<5 => 0
3	0
4	0
5	0
6	0
7	0

 

최대 수용 무게 2에서도 수용할 수 있는 물건이 없기에 모두 0으로 업데이트 된다.

그 다음 순회 $ k = 3 $ 로 넘어가보자.

⬇️ k  \  n  ➡️	0 (무게, 가치)	1 (6, 13)	2 (4, 8)	3 (3, 6)	4 (5, 12)
0	0	0	0	0	0
1	0	0	0	0	0
2	0	0	0	0	0
3	0	3<6 => 0	3<4 => 0	3=3 = 6	dp[3,3] => 6
4	0
5	0
6	0
7	0

 

업데이트 도중 3번째 물건에서 최대 수용 가능 무게와 같게 되면서 처음으로 최대 가치가 바뀌었다!

$ dp[3][3] = 6 $이 된 것이다!

그럼 그다음 4번째 물건에선 어떻게 업데이트 되어야할까? 당연히 이전의 물건까지 업데이트 된 최대 가치를 비교해서 저장해야한다. 현재 같은 경우엔 어차피 [4번째 물건]을 담을 수 없기에, 이전 3번째 물건까지의 최대 가치를 저장해둔다.

 

이제 그 다음 순회인 $ k = 4 $로 넘어가보자.

⬇️ k  \  n  ➡️	0 (무게, 가치)	1 (6, 13)	2 (4, 8)	3 (3, 6)	4 (5, 12)
0	0	0	0	0	0
1	0	0	0	0	0
2	0	0	0	0	0
3	0	0	0	6	6
4	0	4<6 => 0	4=4 => 8
5	0
6	0
7	0

 

업데이트를 진행하면서 2번째 물건의 무게가 최대 수용 가능 무게인 4와 같아서, 최대 가치가 8로 업데이트 되었다! 그럼 이제 그다음 물건인 3번째 물건의 순회를 진행해보자.

⬇️ k  \  n  ➡️	0 (무게, 가치)	1 (6, 13)	2 (4, 8)	3 (3, 6)	4 (5, 12)
0	0	0	0	0	0
1	0	0	0	0	0
2	0	0	0	0	0
3	0	0	0	6	6
4	0	4<6 => 0	4=4 => 8	4>3 => 6 / dp[4][2]=8 ??
5	0
6	0
7	0

 

3번째 물건도 최대 수용 가능 무게인 4보다 작기에, 우리는 선택을 해야한다. 이전의 순회에선 당연하게도 최대 가치가 0이었기 때문에, 이전 물건까지의 최대 가치를 저장했었다.

근데 이번에는 앞에서도 물건(2번 물건)을 담았고, 현재(3번 물건)도 물건을 담을 수 있다.

명심하자, 우리는 챙길 수 있는 무게의 "최대 가치"를 찾고 있다.

예를 들어 너가 보석상에 보석을 털러온 강도라고 생각하자. 내 가방엔 무게가 100키로짜리인 10의 가치를 지닌 금덩이가 있는데, 챙기지 않은 보석 중에 1키로짜리 100의 가치를 지닌 다이아몬드가 있다. 그럼 뭘 챙길것인가? 당연히 둘 다 챙겨야하지않을까?

근데 내가 들 수 있는 무게가 100키로까지라면, 다이아를 챙기기 위해서, 금덩이를 빼고 다이아를 챙길 것이다. 물건이 두개라면 이렇게 간단하지만 물건이 여러개일 때 다시 생각해보자.

• A : 20의 무게 10의 가치
• B : 10의 무게 20의 가치
• C : 15의 무게 20의 가치

내가 챙길 수 있는 최대 무게는 40이라고 생각해보자.

먼저 A를 챙겼다. 가방은 (무게, 가치) = (20, 10) 상태이다.

그 다음 B를 챙기면, 가방은 (30, 30)의 상태이다.

그 다음 C를 챙기려는데, 내가 들 수 있는 무게를 넘어선다, 이제 나는 선택을 해야한다. 

15의 무게를 챙기기 위해서, 뭘 빼지? B를 뺄까, A를 뺄까 당연하게도 빼고, C를 챙겼을 때 최대 가치가 더 높아지는 물건을 챙겨야한다.

그럼 A를 빼고, C를 챙길 것이다. 그럼 가방의 변화는 (30-20, 30-10) -> (10+15, 20+20) = (25, 40) 의 상태가 된다.

다시 문제로 돌아와보자. 문제와 실생활에서 차이점은 우리는 해당 물건을 챙겼을 때 수용 가능 무게마다 모두 저장해놨다는 것이다. 그럼 우리가 물건을 또 담을 수 있다면,

해당하는 물건을 챙길 수 있을만큼의 수용 가능 무게에서의 최대 가치와 현재 담을 물건을 더한 최대 가치와, 그냥 현재 수용가능한 무게에서 이전 물건까지 담았던 최대 무게를 비교할 것이다. 이걸 수식으로 표현해보자.

$$ dp[k][n] = max(dp[k][n-1], dp[k - item[n].weight] + item[n].value) $$

이렇게 표현될 수 있을 것이다. 그럼 다시 테이블을 봐보자.

⬇️ k  \  n  ➡️	0 (무게, 가치)	1 (6, 13)	2 (4, 8)	3 (3, 6)	4 (5, 12)
0	0	0	0	0	0
1	0	0	0	0	0
2	0	0	0	0	0
3	0	0	0	6	6
4	0	4<6 => 0	4=4 => 8	dp[4][2]=8 > dp[4-3][3]+6=0+6=6 => 8
5	0
6	0
7	0

 

현재 수용 가능 최대 무게에서 이전 물건까지 담은 최대 가치가 8(dp[4][2]) 이고, 현재 수용 가능 최대 무게에서, 현재 물건을 담기 위해서 현재 물건의 무게를 뺀 수용 무게에서의 최대 가치 0(dp[4-3][3])에서 현재 물건을 담으면, 현재 물건의 가치를 더해주는 것이니까(+6) 그냥 현재 최대 수용 가능 최대 무게에서 이전 물건까지를 담는 것이 더 높은 가치를 가질 수 있다. 이제 쭉 순회를 진행해보겠다.

⬇️ k  \  n  ➡️	0 (무게, 가치)	1 (6, 13)	2 (4, 8)	3 (3, 6)	4 (5, 12)
0	0	0	0	0	0
1	0	0	0	0	0
2	0	0	0	0	0
3	0	0	0	6	6
4	0	0	8	8	4<5 => dp[4][4-1]=8
5	0
6	0
7	0

 

$ k = 5 $

⬇️ k  \  n  ➡️	0 (무게, 가치)	1 (6, 13)	2 (4, 8)	3 (3, 6)	4 (5, 12)
0	0	0	0	0	0
1	0	0	0	0	0
2	0	0	0	0	0
3	0	0	0	6	6
4	0	0	8	8	8
5	0	5<6 => 0	5>4 => dp[5][2-1] = 0 < dp[5-4][2] + 8 = 8 => 8	5>3 => dp[5][3-1]=8 > dp[5-3][3] + 6 = 6 => 8	5=5 => dp[5][4-1]=8 < dp[5-5][4] + 12 = 12 => 12
6	0
7	0

 

$ k = 6 $

⬇️ k  \  n  ➡️	0 (무게, 가치)	1 (6, 13)	2 (4, 8)	3 (3, 6)	4 (5, 12)
0	0	0	0	0	0
1	0	0	0	0	0
2	0	0	0	0	0
3	0	0	0	6	6
4	0	0	8	8	8
5	0	0	8	8	12
6	0	6=6 => dp[6][1-1]=0 < dp[6-6][1] + 13 = 13 => 13	6>4 => dp[6][2-1]=13 > dp[6-4][2] + 8 = 8 => 13	6>3 => dp[6][3-1]=13 > dp[6-3][3] + 6 = 12=> 13	6>5 => dp[6][4-1]=13 > dp[6-5][4] + 12 = 12 => 13
7	0

 

$ k = 7 $

⬇️ k  \  n  ➡️	0 (무게, 가치)	1 (6, 13)	2 (4, 8)	3 (3, 6)	4 (5, 12)
0	0	0	0	0	0
1	0	0	0	0	0
2	0	0	0	0	0
3	0	0	0	6	6
4	0	0	8	8	8
5	0	0	8	8	12
6	0	13	13	13	13
7	0	7>6 => dp[7][1-1]=0 < dp[7-6][1] + 13 = 13 => 13	7>4 => dp[7][2-1]=13 > dp[7-4][2] + 8 = 8 => 13	7>3 => dp[7][3-1]=13 < dp[7-3][3] + 6 = 14 => 14	7>5 => dp[7][4-1]=14 > dp[7-5][4] + 12 = 12 => 14

 

모든 순회가 끝나면, 아래와 같은 테이블이 완성된다.

⬇️ k  \  n  ➡️	0 (무게, 가치)	1 (6, 13)	2 (4, 8)	3 (3, 6)	4 (5, 12)
0	0	0	0	0	0
1	0	0	0	0	0
2	0	0	0	0	0
3	0	0	0	6	6
4	0	0	8	8	8
5	0	0	8	8	12
6	0	13	13	13	13
7	0	13	13	14	14

그럼 우리가 찾고싶은 최대 수용 무게가 7, 물건 4개를 모두 돌았을 때인, $ dp[7][4] = 14 $가 정답이 될 것이다.

 

반례

내가 과거에도 틀렸고, 이번에도 생각없이 그냥 제출했을 때 틀렸던 반례가 있다.

$ N = 2, K = 4 $

$ items = (1, 1), (2, 2) $

위와 같은 반례인데, 테이블을 만들어서 봐보자.

⬇️ k  \  n  ➡️	0 (무게, 가치)	1 (1, 1)	2 (2, 2)
0	0	0	0
1	0	1	1
2	0	1	2
3	0	1	3
4	0	1	3

이 반례는 k = 0, n = 0일때 최대 가치를 0으로 저장해두지 않고, 풀게되면 문제를 일으킨다.

위의 테이블은 설명과 같이 최대 가치 0으로 저장해둔 테이블이다. 하지만 나는 처음에 간단하게 해결할 때, 그 처리를 하지않아서 문제가 발생했다.

처음엔 그냥 수용 가능 최대 무게만 0일 때를 고려했다. 그리고 뒤의 처리는 똑같이 진행했다. 틀린 알고리즘 갱신과정 테이블은 아래와 같다. 

⬇️ k  \  n  ➡️	0 (1, 1)	1 (2, 2)
0	0	0
1	1=1 => dp[1][0-1] ??
2
3
4

dp[1][0]을 바꿀 때 뭔가 이상하지 않은가?? 아이템의 갯수에 대해서 0에 대한 최대 가치가 없다면, 저렇게 이상한 위치를 참조하는 문제가 발생한다. 그래서 반례처리에 대해서 문제가 생겼다.

 

또한 $ (K + 1, N + 1) $ 로 구성한다면, 아이템을 참조할 때 인덱스 에러도 조심하여 코드를 작성하자.

코드

N, K = map(int, input().split()) # 물건 갯수, 버틸 수 있는 최대 무게
stuff = [] # [무게, 가치]

for _ in range(N):
    stuff.append(list(map(int, input().split())))
    
dp = [[0 for _ in range(N+1)] for _ in range(K+1)] #  # [버틸 수 있는 최대 무게, 물건 갯수]

# Knapsack Algorithm
for i in range(K+1): # 버틸 수 있는 최대 무게에서
    for j in range(N+1):
        if i == 0 or j == 0: # 버틸 수 있는 최대 무게가 0이거나, 0번째 물건의 가치까지는 0으로 초기화
            dp[i][j] = 0
        elif i < stuff[j-1][0]: # 만약 버틸 수 있는 최대 무게 < 현재 순회하는 물건의 무게보다 작다면
            dp[i][j] = dp[i][j-1] # 이전까지 버텼던 무게까지의 가치를 그대로 가져옴
        else: # 만약 버틸 수 있는 최대 무게 >= 현재 순회하는 물건의 무게라면
            dp[i][j] = max(dp[i][j-1], dp[i-stuff[j-1][0]][j-1] + stuff[j-1][1]) # 이전까지 버텼던 무게까지의 가치와, 현재 물건을 넣었을 때의 가치를 비교하여 더 큰 값을 가져옴            
print(dp[K][N])