(Python/파이썬) 백준 12865번 - 평범한 배낭
문제출처: https://www.acmicpc.net/problem/12865
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
1. 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
n, k = map(int, input().split())
item = [[0,0]]
d = [[0]*(k+1) for _ in range(n+1)]
for i in range(n):
item.append(list(map(int, input().split())))
for i in range(1, n+1):
for j in range(1, k+1):
w = item[i][0]
v = item[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])
|
cs |
2. 해결과정
냅색(knapsack)알고리즘 이라고 불리는 문제이다.
배낭의 용량이 정해져 있을 때 , 최대한의 가치를 가질 수 있도록 배낭을 싸야하는 문제이다.
냅색 알고리즘은 담을 수 있는 물건이 나눌 수 있는지 여부에 따라 달라지게 된다.
담을 수 있는 물건이 나눠지면(ex. 설탕 몇 g, 소금 몇 g) 분할 가능한 배낭 문제가 되고
담을 수 있는 물건이 나눠지지 않는다면 0-1 배낭 문제가 된다.
위 문제는 0-1 배낭 문제이다.
알고리즘을 설명해주면, x축에는 우선 k까지의 가방의 무게, y축에는 물건 n개 개수 만큼의 배열을 만들어준다.
행을 차례대로 돌면서
1) 현재 배낭의 허용 무게보다 넣을 물건의 무게가 더 크면 넣지 않음 --> j<weight : d[i][j]=d[i-1][j]
2) 그렇지 않으면 더 큰 가치 선택
- 현재 넣을 물건의 무게만큼 배낭에서 뺌. 현재 물건 넣음 --> 그 무게의 배낭이 가지는 최대 가치가 이미 저장됨
- 현재 물건 넣지 않고 이전 배낭 그대로
--> d[i][j] = max( d[i-1][ j-weight ]+value ), d[i-1][j] )
3. 느낀점
진심 엄청 어려웠다. 그래서 다른 사람들이 어떻게 풀었는지도 엄청 찾아봤다. dp의 기본 문제 중 하나라고 하는데 기본도 못푸는 것 같아서 약간 매우 현타가 왔다. 그래도 한발 한발 천천히 노력하다보면 이런 문제도 풀 수 있지 않을까,,? ㅜㅜㅜ