냅색 알고리즘
냅색 알고리즘은 유명한 DP 문제 중 하나입니다.
냅색 알고리즘은 두가지로 나뉩니다.
Fraction Knapsack
Fraction Knapsack 문제는 물건의 가격을 무게로 나누어 무게 대비 가격이 비싼 순서로 물건을 정렬해서 넣으면 쉽게 해결할 수 있습니다.
남은 배낭이 감당할 수 있는 무게보다 물건의 무게가 많이 나가면 잘라서 넣으면 됩니다.
= greedy로 해결 가능!
0-1 Knapsack
0-1 Knapsack 문제는 물건을 자를 수 없기 때문에 물건, 물건의 무게, 물건의 가격, 배낭의 남은 용량을 모두 고려해야 합니다.
= dp로 해결 가능!
0-1 Knapsack
가방에 담을 수 있는 무게엔 한계가 있고, 각 물건엔 가치가 정해져있습니다.
가방에 최대치로 물건을 담았을 때, 최대의 가치값을 구하는 문제입니다.
언듯 그리디 알고리즘과 비슷해보이지만 최적의 해가 나오지 않을 때도 있습니다.
가방에 15kg까지 담을 수 있고, 세가지 물건이 있다. 이때 가치를 최대로 가지려면 어떤 물건을 담아야할까?
[물건 A] 가치: 10, 무게: 13kg
[물건 B] 가치: 6, 무게: 6kg
[물건 C] 가치: 5, 무게: 6kg
그리디 알고리즘
가치를 최대로 갖도록 그때그때 최선의 선택을 하기때문에 물건 A를 담고 끝이 난다.
정답
물건 A를 담지 않고, B와 C를 담는다.
오히려 특정 물건을 담지 않았을 때가 최선의 선택일 수 있음을 고려해주는 것이 냅색 알고리즘의 핵심인 것 같습니다.
냅색 알고리즘은 동적프로그래밍 (dp)를 이용하면 문제를 해결할 수 있습니다.
가방에 최대 M kg 까지 담을 수 있을 때,
dp[i][j] = 가방에 담은 물건의 무게 합이 i일 때, 처음 j개의 물건 중 담을 수 있는 최대 가치 ( 1 < i <=M)
- i가 현재 물건의 무게 w보다 작을 때
현재 물건을 담을 수 없으므로 이전의 값을 복사한다.
dp[i][j] = dp[i][j-1] - i가 현재 물건의 무게 w와 같거나 클 때
현재 물건을 담을 수 있다.
물건을 담았을 때와 담지 않았을 때의 가치를 비교해준 뒤 더 큰 값을 할당해준다.
현재 물건의 가치는 v 이다.
dp[i][j] = max( dp[i][j-1] , dp[i-w][j-1] + v)
물건의 최대 가치는 dp[가방 크기][물건의 개수] 로 구할 수 있다.
평범한 배낭 성공
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 512 MB 98579 36602 23599 35.483%
문제
이 문제는 아주 평범한 배낭에 관한 문제이다.
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 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)가 주어진다.
입력으로 주어지는 모든 수는 정수이다.
출력
한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.
예제 입력 1
4 7
6 13
4 8
3 6
5 12
예제 출력 1
14
유명한 알고리즘이다 보니 백준에도 문제가 있어서 동적 프로그래밍을 이용해 풀어보았습니다
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
# d[i][j] : i번째 물건까지 고려했을 때, 용량 j를 가지는 배낭에 담을 수 있는 물건들의 최대 가치
d = [[0] * (k + 1) for _ in range(n)]
weight = []
value = []
for _ in range(n):
w, v = map(int, input().split())
weight.append(w)
value.append(v)
# 0/1 Knapsack 문제를 해결하는 DP 알고리즘
for i in range(n):
for j in range(k + 1):
# 현재 물건을 배낭에 넣을 수 있는 경우
if j >= weight[i]:
# 이전 물건(i-1)까지 선택한 경우와 현재 물건(i)을 선택한 경우 중, 최대 가치를 선택
d[i][j] = max(d[i-1][j], d[i-1][j-weight[i]] + value[i])
# 현재 물건을 배낭에 넣을 수 없는 경우, 이전 물건(i-1)까지 선택한 경우의 최대 가치와 동일
else:
d[i][j] = d[i-1][j]
# 물건을 전부 고려했을 때, 용량 k를 가지는 배낭에 담을 수 있는 물건들의 최대 가치 출력
print(d[n-1][k])풀면서 어디에 DP를 활용해서 풀까, 리스트의 좌표는 어떤식으로 다가갈까를 고민하면서 풀었습니다
다이내믹 프로그래밍이 어려운 가장 큰 이유는 일반적인 직관과는 다른 사고방식을 필요로 한다는 점이다. 특히 사고과정을 면대면이 아닌 책으로 기술한다는 것은 더욱 어려운 일일 것입니다.
내일은 오늘보다 난이도가 높은 동적 프로그래밍 활용 문제와 그리디 알고리즘의 기초에 대해 공부해 볼 예정입니다
