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

문제에서 주어진 바와 같이 우리는 준서가 버틸 수 있는 무게에 맞추어 최대 가치를 가지도록 배낭에 물건을 담아야 한다. 이를 위해 knapsack 알고리즘을 활용할 수 있다. 만약 다음과 같이 물건과 가치가 주어졌다고 할 때 버틸 수 있는 무게를 10으로 놓고 knapsack 알고리즘이 어떻게 진행되는지 살펴보자.

물건	1	2	3	4
무게	5	6	4	3
가치	20	10	30	40

knapsack 알고리즘을 위해서는 dp table을 생성해야 한다. 이를 위해 (물건의 개수+1) ×(버틸 수 있는 무게+1) 만큼의 크기를 가진 table을 생성한다. 이때 (물건의 개수+1) 만큼의 행을 가지도록 생성한 이유는 knapsack알고리즘을 적용하기 위해서다. 

배낭 용량	0	1	2	3	4	5	6	7	8	9	10
물건	0	0	0	0	0	0	0	0	0	0	0
물건 1	0	0	0	0	0	0	0	0	0	0	0
물건 2	0	0	0	0	0	0	0	0	0	0	0
물건 3	0	0	0	0	0	0	0	0	0	0	0
물건 4	0	0	0	0	0	0	0	0	0	0	0

각 i행 j열에 있는 원소의 의미는 다음과 같다.

• 물건 1~i까지 탐색했을 때 j만큼의 무게를 담는 경우 담을 수 있는 물건의 가치의 최대값

따라서 물건 i를 탐색할 때 물건 i의 무게(w)보다 담을 수 있는 무게가 더 크거나 같다면 물건 i를 배낭에 넣어볼 수 있으므로 우리는 아래 두 값을 비교하여 i행 j열의 원소를 채울 수 있다.

• 물건 1~(i-1)까지 탐색했을 때 j-w만큼의 무게를 담는 경우 담을 수 있는 물건의 가치의 최대값과 물건 i의 가치의 합
• 물건 1~(i-1)까지 탐색했을 때 j만큼의 무게를 담는 경우 담을 수 있는 물건의 가치의 최대값

반대로 물건 i의 무게(w)보다 담을 수 있는 무게가 더 작다면 물건 i를 배낭에 넣을 수 없으므로 우리는 i해 j열에 다음 값을 넣어야 한다.

• 물건 1~(i-1)까지 탐색했을 때 j만큼의 무게를 담는 경우 담을 수 있는 물건의 가치의 최대값

이제 예시를 살펴보면서 해당 알고리즘을 적용해보자. 먼저 물건 1의 무게가 5이므로 담을 수 있는 무게가 5 이상일 때부터 물건 1을 담을 수 있다. 따라서 dp[0][0]+(물건 1의 가치)와 dp[0][5]를 비교하여 더 높은 값을 dp[1][5]에 저장한다. 이후 dp[1][6]~dp[1][10]까지 동일한 방식으로 채우게 되면 dp table은 아래와 같아진다.

배낭 용량	0	1	2	3	4	5	6	7	8	9	10
물건	0	0	0	0	0	0	0	0	0	0	0
물건 1	0	0	0	0	0	20	20	20	20	20	20
물건 2	0	0	0	0	0	0	0	0	0	0	0
물건 3	0	0	0	0	0	0	0	0	0	0	0
물건 4	0	0	0	0	0	0	0	0	0	0	0

물건 2의 무게는 6이고 가치는 10이다. 따라서 담을 수 있는 무게가 6보다 작은 경우에는 dp[1]의 행과 동일하게 채워주면 된다. 담을 수 있는 무게(j)가 6보다 크거나 같은 경우에는 dp[1][j]와 dp[1][j-w]+10 중 더 큰 값으로 table을 채우게 된다.

배낭 용량	0	1	2	3	4	5	6	7	8	9	10
물건	0	0	0	0	0	0	0	0	0	0	0
물건 1	0	0	0	0	0	20	20	20	20	20	20
물건 2	0	0	0	0	0	20	20	20	20	20	20
물건 3	0	0	0	0	0	0	0	0	0	0	0
물건 4	0	0	0	0	0	0	0	0	0	0	0

이후 물건 3과 물건 4를 동일한 방법으로 탐색하게 되면 아래와 같은 table이 만들어진다.

배낭 용량	0	1	2	3	4	5	6	7	8	9	10
물건	0	0	0	0	0	0	0	0	0	0	0
물건 1	0	0	0	0	0	20	20	20	20	20	20
물건 2	0	0	0	0	0	20	20	20	20	20	20
물건 3	0	0	0	0	30	30	30	30	30	50	50
물건 4	0	0	0	40	40	40	40	70	70	70	70

결국 우리가 원하는 값은 물건 1~4까지 탐색했을 때 담을 수 있는 무게가 10인 경우의 물건 가치의 최대값이므로 dp[4][10]값을 반환해주면 된다. 위 knapsack 알고리즘을 코드로 구현하면 아래와 같이 구현할 수 있다.

import sys
input = sys.stdin.readline
'''
n: 물품 개수, limit: 준서가 버틸 수 있는 무게
items: 각 물건의 무게와 가치를 담는 리스트
'''
n, limit = map(int, input().split()) 
items = list([(0, 0)]) 

# (무게, 가치)를 입력받고 items리스트에 넣어준다.
for _ in range(n):
    items.append(tuple(map(int, input().split())))

# dp table을 생성해준다.
dp = [[0 for _ in range(limit+1)] for _ in range(n+1)]

# knapsack 알고리즘을 수행한다.
for row in range(1, n+1):
    weight, value = items[row]
    for col in range(1, limit+1):
        if weight <= col:
            dp[row][col] = max(dp[row-1][col], dp[row-1][col-weight]+value)
        else:
            dp[row][col] = dp[row-1][col]

# dp의 마지막 원소를 출력한다.
print(dp[-1][-1])

 

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

12865번: 평범한 배낭