가방 허용 무게가 정해서 있을 때 가방에 넣을 수 있는 물건들의 최대값을 구할 때.
최대 가치를 가지는 물건을 넣는 식으로 greedy 알고리즘으로 문제를 해결하려고 하면
해결 할 수 없다.
ex ) 가방의 허용 무게 7kg. 물건들 (6kg 13) (4kg, 8) (3kg, 6) (5kg, 12) 일 때 (4kg, 8) (3kg, 6) 담는 경우가 정답인데
그리디 알고리즘으로 해결하려고 하면 (6kg 13) 나옴
분할가능 냅색 알고리즘
- 담을 물건이 소금 등 분할 가능 할 때 무게당 가치로 정렬하고 그리디 알고리즘을 수행하면 해결 가능
0-1냅색 알고리즘(분할 불가능)
- 담을 물건이 나누어 지지 않을 때 사용하는 알고리즘
- DP 알고리즘으로 점화식 이용
- 2차원 리스트 L 를 만든다. (row : 물건 갯수, col : 가방 허용 무게)
- 각 물건 갯수, 가방 허용 무게 일 때 최대 가치를 리스트에 담아보면 L(n, k) 가 정답.
- 무게가 w 가치가 v인 물건을 넣을 때 점화식 : L(n, k) = max(L[n-1][k], L[n-1][k-w] + v)
'자료구조와 알고리즘' 카테고리의 다른 글
[python] 다익스트라 최단 경로 알고리즘 / 플로이드 워셜 알고리즘 (0) | 2022.01.21 |
---|---|
[python] 힙 구조 모듈 heapq (0) | 2022.01.06 |
자료구조와 알고리즘 (0) | 2022.01.06 |
[python] 너비우선탐색, 깊이우선탐색(bfs, dfs) (0) | 2022.01.05 |