[백준 12865] 평범한 배낭 - python
원본 문제 링크 : 평범한 배낭
문제
이 문제는 아주 평범한 배낭에 관한 문제이다.
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.
입력
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.
입력으로 주어지는 모든 수는 정수이다.
출력
한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.
풀이
해당 문제는 0-1 배낭 문제다. 0-1 배낭 문제에 대한 자세한 설명은 링크 참조
DP의 ‘분기 기준점’을 무엇으로 잡아야 할지가 중요한데, 문제를 읽고 떠오를 수 있는 기준은 다음과 같다.
- 아이템의 개수
- 아이템이 1개일 때 최대 가치가 되는 경우..
- 배낭의 최대 허용 중량
- 중량이 1일 때 최대 가치가 되는 경우..
- i번째 아이템까지 살펴보았을 때
- 1번째 아이템까지 살펴보았을 때 최대 가치가 되는 경우..
어떤 문제를 DP로 풀기 위해서는 최적 부분 구조와 같은 DP의 최적 조건을 만족해야 한다.
배낭 문제의 경우 기준을 하나만 두어서는 최적의 해를 계산하는 점화식을 만드는 것이 불가능하다.
ex : 가방의 무게가 같더라도 안에 넣은 아이템의 종류에 따라 미래의 가치가 달라질 수 있음
핵심 아이디어는 행(row)이 item index, 열(col)이 무게(w)인 table(2차원 배열)을 구성하는 것이다. 다차원 배열을 통해 여러 조건을 동시에 활용할 수 있게 되고, 해당 table을 DP 방식을 통해 효율적으로 채울 수 있다.
점화식의 형태는 특정 무게 $w_j$ 에서 $item_i$ 를 넣는 경우와 넣지 않는 경우, 더 가치가 큰 것을 table에 기록하는 것이다. 점화식 유도 과정은 위의 링크를 참고하는 것이 좋다.
분할 가능한 배낭 문제(fractional knapsack problem)와 같이 table에 기록하기 전 별도의 정렬 과정은 필요하지 않다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
#Bottom-Up
N, K = map(int,input().split())
item_li = [[0,0]]+[list(map(int,input().split())) for _ in range(N)] #[0] : 무게 #[1] : 가치
#print(item_li)
P = [[0]*(K+1) for _ in range(N+1)]
for i in range(1,N+1) : #i : item 인덱스이면서 P의 행 인덱스
for j in range(1,K+1) : #무게를 1부터 K까지 #j : P의 열 인덱스, 무게
if item_li[i][0] > j :
P[i][j] = P[i-1][j] #넣을 수 없는 경우, 기존의 해당 아이템을 제외한 결과를 그대로 사용
else :
P[i][j] = max(P[i-1][j], P[i-1][j-item_li[i][0]]+item_li[i][1]) #점화식
#print(P)
print(P[N][K])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Top-Down
def knapsack(i, j):
if i == 0 or j == 0:
return 0
if P[i][j] != -1:
return P[i][j]
if item_li[i][0] > j:
P[i][j] = knapsack(i-1, j)
else:
P[i][j] = max(knapsack(i-1, j), knapsack(i-1, j-item_li[i][0]) + item_li[i][1])
return P[i][j]
N, K = map(int, input().split())
item_li = [[0, 0]] + [list(map(int, input().split())) for _ in range(N)]
P = [[-1] * (K+1) for _ in range(N+1)]
print(knapsack(N, K))
제출 결과 기준, 공간복잡도, 시간복잡도 모두에서 Top-Down 방식이 Bottom-Up보다 훨씬 나은 결과를 보였다.