[백준] 12865 평범한 배낭(Python 파이썬)

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

12865번: 평범한 배낭

문제 설명

이 문제는 아주 평범한 배낭에 관한 문제이다.

흔히, 냅색(Knapsack) 알고리즘이라고 불리는 문제이다.

배낭의 용량이 정해져 있을 때, 최대한의 가치를 가지도록 배낭을 싸야 한다.

주어진 물건들의 용량과 가치를 고려하여 주워담을지 말지 정하는 문제이다.

---

풀이 과정

먼저, 내 배낭이 버틸 수 있는 용량이 7이라고 하자. K=7 이다.

그리고 물건이 4개 있는데 (N = 4), 각각의 무게와 가치가 다음 표와 같다고 하자.

무게	6	4	3	5
가치	13	8	6	12

첫 번째 물건부터 살펴보면 무게가 6인데, 내 배낭은 현재 0 무게이므로 담을 수 있다.

두 번째 물건을 살펴보면, 무게가 4이다. 첫 번째 물건을 담았으면 4+6 > 7 (배낭의 최대) 이므로 담을 수 없고

첫 번째를 버리던가, 두 번째를 담지않던가 선택을 해야한다.

 

지금 당장은 첫 번째를 가져가는게 맞지만, 후에는 어떤 것을 담는것이 더 가치있는지 모른다.

그래서, 더 가치있는 것을 판별해줄 알고리즘을 짜야 한다.

 

그럼, 이렇게 생각해보자.

N * K 의 2차원 배열 d[n][k]를 만들어 각각의 물건을 선택할 때 마다 최대 가치를 판별해줄 수 있도록 하자.

d[n][k]는 N번째 물건 까지 살펴보았을 때, 무게가 K인 배낭의 최대 가치 이다.

 

물건을 배낭에 담을 때,

① 현재 배낭의 허용 무게보다 넣을 물건의 무게가 더 크다면 넣지 않는다.

② 그렇지 않다면, 다음 중 더 나은 가치를 선택하여 넣는다

    2-1) 현재 넣을 물건의 무게만큼 배낭에서 뺀다. 그리고 현재 물건을 넣는다.

    2-2) 현재 물건을 넣지않고 이전 배낭 그대로 가지고 간다.

 

위 과정을 식으로 나타내면 다음과 같다.

현재 담을 물건의 인덱스를 i, 현재 가방 허용 용량이 j, 현재 담을 물건의 무게를 weight, 가치 value라고 할 때,

① j < weight : d[i][j] = d[i-1][j]

② d[i][j] = max( d[i-1][ j-weight ]+value ), d[i-1][j] )

 

2-1)의 과정에서, 현재 넣을 물건의 무게만큼 배낭에서 뺀다고 한 부분에 이런 의문점이 들 수 있다.

현재 넣을 무게와 똑같은 무게의 물건이 없으면, 어떻게 빼는가? 물건이기 때문에 쪼개지 못하는데?

 

하지만, 현재 넣을 물건의 무게만큼 뺀 배낭에는,

그 무게의 배낭이 가지는 최대 가치가 저장되어 있다. 그래서 상관없다.

 

예를 들어, 현재 무게 7의 배낭에 무게 4 짜리 물건을 넣으려고 한다면

무게 4를 배낭에서 뺀 후에 그 때의 배낭가치에 현재 물건을 넣었을 때의 가치를 더해주어야 하는데,

 

내 배낭속에는 무게 4짜리 물건이 없고, 무게 3짜리밖에 없다고 하자.

하지만 d[n][3]에는 이미 무게 3인 배낭이 가지는 최대 가치가 저장되어 있고

d[n][4]에는 무게 4인 배낭이 가지는 최대 가치가 저장되어 있기 때문에 상관 없는 것이다.

 

직접 표를 그려보면 더 이해하기 쉬울 것이다.

 

이를 이용한 최종 코드는 다음과 같다.

n, k = map(int, input().split())

thing = [[0,0]]
d = [[0]*(k+1) for _ in range(n+1)]

for i in range(n):
    thing.append(list(map(int, input().split())))

for i in range(1, n+1):
    for j in range(1, k+1):
        w = thing[i][0]
        v = thing[i][1]

        if j < w:
            d[i][j] = d[i-1][j]
        else:
            d[i][j] = max(d[i-1][j], d[i-1][j-w]+v)

print(d[n][k])

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !