냅색 알고리즘? (🔗 참고)
냅색 알고리즘은 유명한 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)
1) i가 현재 물건의 무게 w보다 작을 때
- 현재 물건을 담을 수 없으므로 이전의 값을 복사한다.
dp[i][j] = dp[i][j-1]
2) i가 현재 물건의 무게 w와 같거나 클 때
- 현재 물건을 담을 수 있다.
- 물건을 담았을 때와 담지 않았을 때의 가치를 비교해준 뒤 더 큰 값을 할당해준다.
- 현재 물건의 가치는 v 이다.
dp[i][j] = max( dp[i][j-1] , dp[i-w][j-1] + v)
물건의 최대 가치는 dp[가방 크기][물건의 개수] 로 구할 수 있다.
