문제
문제 링크 : 백준 12865
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다.
두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.
한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.
접근
잘못된 접근
처음 문제를 접했을 땐 위의 사진처럼 접근했다.
위의 과정은 점화식이 없을 뿐더러 접근하는 근거가 부족하다.
그리고 매번 최적해를 찾아낼 수 없다.
새로운 접근
이 블로그(참조 링크) 에서 배낭 문제라는 것을 알게 되었고, 문제를 해결하는데 참고했다.
해당 문제는 배낭문제로 배낭에 담을 수 있는 최대 무게가 설정되어있고 최대 무게까지 담을 수 있을 때, 가치의 합이 최대가 되도록 짐을 고르는 문제이다.
배낭문제 알고리즘은
- 담을 수 있는 물건이 나누어 질 때 : 분할가능 배낭문제(Fractional Knapsack Problem)
- 담을 수 있는 물건이 나누어 질 수 없을 때 : 0-1 배낭문제(0-1Knapsack Problem)
해당 문제는 0-1 배낭문제의 경우다.
풀이
우선 2차원 배열을 k+1개의 행(가방용량)과 n+1개의 열(물건)로 선언해줬다. (배열 상 i,j의 위치를 i-1,j-1번째가 아닌 i,j로 보기위해서)
그리고 아래의 순서로 2차원 배열을 2중 반복문으로 접근해 배열 끝까지 진행한다.
- 입력받은 배열에서 짐 하나(weight-무게, value-가치)를 꺼낸다.
- 현재의 가방용량과 짐 무게에 따라 나뉜다.
2-1. 가방용량보다 크다면 넣을 수 없기 때문에 이전물건의 같은 무게인 값을 현재 물건에 넣어준다.
2-2. 가방용량보다 작거나 같다면 넣을 수 있기 때문에 현재 추가하는 물건의 가치에 따라 나뉜다.
2-2-1. 현재 추가하는 물건의 가치를 이전 물건의 가치에 더하고, 추가하는 물건의 무게만큼 빼준다.
2-2-2. 현재 추가하는 물건의 가치를 넣지않고 이전 물건의 같은 무게인 값을 가져온다.
2-3. 2-2-1) 와 2-2-2)의 가치 중 큰 값을 현재 최대 무게 물건에 넣어준다. - 배열의 마지막에 저장된 값을 출력한다.
따라서 식으로 표현하자면
가방용량보다 현재 짐의 무게가 크다면
dp[현재물건][가방용량] = dp[이전물건][가방용량]
(dp[i][j] = dp[i - 1][j])
아니라면
dp[현재물건][가방용량] = max(dp[이전물건][가방용량 - 무게] + 가치, dp[이전물건][가방용량])
(dp[i][j] = max(dp[i - 1][j - weight] + value, dp[i - 1][j]))
을 찾을 수 있다!
식을 표로 표현했을 때 아래와 같이 저장되며,
위 식의 마지막인 dp[4][7]을 출력한다.
정답 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 12865
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
w = [[0, 0]]
dp = [[0 for i in range(k + 1)] for j in range(n + 1)]
for i in range(n):
w.append(list(map(int, input().split())))
for i in range(1, n + 1):
for j in range(1, k + 1):
weight = w[i][0]
value = w[i][1]
if j < weight:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j - weight] + value, dp[i - 1][j])
print(dp[n][k])
dp에 저장된 결과
1
2
3
4
5
6
7
8
9
print(dp)
[
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 13, 13],
[0, 0, 0, 0, 8, 8, 13, 13],
[0, 0, 0, 6, 8, 8, 13, 14],
[0, 0, 0, 6, 8, 12, 13, 14]
]
느낀점
배낭문제를 되게 오랜만에 풀어봐서 기억이 가물가물했고 두 가지의 유형으로 나뉜다는 것도 알게 되었다.
배낭문제 알고리즘을 정리해놔야겠다. 틀은 비슷하기에 그냥 외우는 것도… 나쁘진 않겠다..