[boj 12865][Python] 평범한 배낭

문제 링크

알고리즘에 있어서 대표적인 유형인 배낭 문제(napsack algorithm) 이다.

알고리즘 수업을 들었던 기억을 잘 떠올려 아래와 같이 정리하였다.

배낭 문제 접근하기

우선 접근하기 위해 첫번째 예제를 살펴보자.

물건 4개, 무게 제한 K=7
w  v
6 13
4 8
3 6
5 12

일단 그리디 알고리즘으로 접근해보자. 가장 v가 높으면서 w가 k 이하인 물건은 첫번째 물건이다. 이때 w=6, v=13이다.

그러나 최적의 해는 2, 3번째 물건을 넣는 것이다. w=4+3, v=8+6=14이다.

그럼 단순히 v를 기준으로 따지는 게 아니라, 무게 대비 가치를 따져보면 어떨까?

w v    V per W
6 13     2.1x
4 8      2
3 6      2
5 12     2.4

무게 대비 가치가 가장 높은 물건은 네번째 물건이다. 이때 w=5, v=12이다.

역시 최적의 해가 아니다.

따라서 greedy한 접근으로는 이 문제를 해결할 수 없다.

만약에 이 물건들이 쪼개진다면 이 방법으로 풀 수 있었을 것이다.

DP: Dynamic Programming을 이용하여 접근한다.

dp[i] = max (dp[k-i] + dp[i] ) 모든 0<i<k에 대해

난 이렇게 생각하고 돌렸는데, 예제는 맞았으나 결과는 시간초과!!!!

문제의 최대 k가 십만임을 고려하면, 이 방법으로는 안 된다는 걸 생각해볼 수 있다. (대략 100000*100000의 경우의수를 따져야 함.)

다시 접근해보자.

• d[i][j] = i번째까지의 물건으로 배낭 구성 시, 무게 j 제한에 대한 최대 가치
  0. i번째 물건 무게가 j보다 크면 i번째 물건은 넣을 수 없다. 따라서 d[i][j] = d[i-1][j]
  1. i번째 물건을 고려. max(d[i-j][j], d[i-1][j-(i번째물건무게)] + i번째 물건 가치)
  따라서 d[i][j] = max(0번경우, 1번경우) 이다.

코드

n, k = map(int, input().split())
items = []
for _ in range(n):
    v, w = map(int, input().split())
    items.append((v, w))

# 입력 끝

# dp

dp = [[0 for _ in range(k+1)] for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, k+1):
        w, v = items[i-1]
        if j < w:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)

print(dp[n][k])

dp가 약간만 복잡해져도 어려웠다. 제대로 기억하자.