냅색 알고리즘

uoayop·2021년 5월 13일
2

알고리즘 스터디

목록 보기
7/11
post-thumbnail

냅색 알고리즘? (🔗 참고)

냅색 알고리즘은 유명한 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[가방 크기][물건의 개수] 로 구할 수 있다.

profile
slow and steady wins the race 🐢

0개의 댓글