백준 12865 - 평범한 배낭 풀이

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

DP 문제를 풀면서 기억해두면 좋을 케이스라 기록해두기로 했다.

 

문제 정의

배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 구하는 문제이다.

완전탐색을 하기에는 경우의 수가 너무 많고, 중복되는 계산이 반복되기 때문에 dp로 풀어야겠다고 생각했다.

 

1. 상태 정의

dp[i] = 무게가 i일 때 가치합의 최대값

 

2. 점화식 세우기

# item은 [weight, value]로 구성
dp[i] = max(dp[i], dp[i - item[0]] + item[1])

현재 배낭 용량이 id일 때,

1) 이 물건을 안 넣었을 때 기존 i무게 에서의 최대 가치와

2) 이 물건을 넣었을 때의 최대 가치를

비교해서 더 큰 값을 선택한다.

 

3. 초기값 설정

어차피 존재하지 않는 경우의 무게는 고려할 필요가 없기 때문에 초기값을 굳이 세워둘 필요는 없다.

# 전부 0으로 초기화하면서 생성
dp = [0] * (weight + 1)

 

이렇게 문제를 풀었더니 테스트케이스가 통과하길래 정답인 줄 알았는데 오답이었다.

테스트케이스를 직접 바꿔가며 로그를 찍어본 결과 한 가지 문제가 있었다.

 

같은 물건을 2번 이상 담는 경우의 수가 존재

 

이전에 풀었던 동전 담기와 같은 문제들은 같은 선택지를 여러번 선택해도 문제가 되지 않았지만,

배낭 문제는 한 번 선택한 물품은 다시 선택할 수 없다.

 

오답 코드를 보고, 정방향으로 반복문을 돌면 어떤 문제가 생기는지 살펴보자.

# 오답 코드
# 첫번째 아이템의 weight 부터 순차적으로 dp를 채워간다.
N, max_weight = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]

dp = [0] * (max_weight + 1)

for weight, value in items:
    for i in range(weight, max_weight + 1):
        dp[i] = max(dp[i], dp[i - weight] + value)

print(dp[max_weight])

 

여기서 반복문을 살펴보자.

for i in range(weight, max_weight + 1):

작은 무게부터 큰 무게로 가면서 dp를 갱신하고 있다.

이러면 같은 물건을 처리하는 중에, 방금 갱신한 값을 또 바로 참조하게 된다.

 

예시를 통해 살펴보자.

무게 = 3, 가치 = 4인 물건이 딱 하나있고, 배낭의 최대 무게가 6이라고 가정하자.

dp의 초기값은 모두 0으로 채워져있다. 이제 정방향으로 반복문을 돌아보자.

 

i = 3

dp[3] = max(dp[3], dp[0] + 4) = 4

i를 1씩 증가시키면서 dp[i] 값을 채워나간다.

그러다가 i가 6일때 문제가 발생한다.

 

i = 6

dp[6] = max(dp[6], dp[3] + 4) = 8

dp[3]은 방금 같은 물건으로 만든 값 4가 들어있기 때문에, dp[6]은 무게가 3인 물건을 두 번 넣은 것처럼 계산되어 8이 된다.

하지만 배낭 문제는 동일한 물건을 두번 담는것이 불가능하기 때문에 사실은 가능하지 않은 경우의 수이다.

이를 해결하기 위해서 두 가지 방법을 사용할 수 있다.

 

1. 역방향으로 탐색하기

dp[6] = max(dp[6], dp[3] + 4)

큰 쪽부터 역순으로 내려오면, dp[i - weight]는 아직 이번 물건으로 갱신되기 전의 값이다.

즉, 현재 물건을 넣을 때 참고하는 값은 이전 물건들만 고려한 상태가 된다!

 

i = 6

dp[6] = max(dp[6], dp[3] + 4)

여기서 dp[3]은 아직 0이다. i = 3을 아직 처리하지 않았기 때문이다.

그래서 dp[6] = 4가 된다.

이후 i = 3까지 dp[i]는 4로 초기화된다.

 

2. 2차원 배열 풀이

지금처럼 상태가 2개 필요한 문제에서는 2차원 배열 풀이를 고려해볼 수 있다.

현재 문제에서는

- 몇 번째 물건까지 고려했는지

- 현재 허용 무게가 얼마인지

를 상태로 둘 수 있다.

 

이를 토대로 문제정의를 해보면 다음과 같다.

 

1. 상태 정의

dp[i][w] = 앞에서부터 i개 물건만 고려했을 때, 배낭 허용 무게가 w일 때 얻을 수 있는 최대 가치

 

2. 점화식 세우기

dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight] + value)

여기서 항상 i - 1 만 참고하기 때문에, 같은 물건을 두 번 쓸 일이 없다.

여기서, 현재 물건이 너무 무거워서 못 넣는다면, 현재 물건은 없는 셈 치고 이전 결과를 그대로 가져온다.

if w < weight:
  dp[i][w] = dp[i - 1][w]

 

3. 초기값 설정

위와 동일하다.

 

전체 코드

N, K = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

dp = [[0] * (K + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    weight, value = items[i - 1]

    for w in range(K + 1):
        if w < weight:
            dp[i][w] = dp[i - 1][w]
        else:
            dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight] + value)

print(dp[N][K])

-> 각 물건들을 추가할때마다 i를 증가시키고, 항상 i - 1번째 값들을 참고하기 때문에, 같은 물건을 두 번 담을 수가 없다.