배낭 문제 (0/1 Knapsack Problem)
배낭 문제란 배낭에 담을 수 있는 무게의 최대값이 정해져 있고,
일정한 가치와 무게가 정해져있는 짐들을 배낭에 닮을 때,
가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.
0/1 knapsack = 물건 못 쪼갬
Fraction knapsack = 물건 쪼갤 수 있는 문제
사실 kanpsack 문제는 dp에 있어야...
- 예시 문제
- 해결법
- 시간 복잡도 , 공간복잡도
반응형
'미가공 필기(알고리즘)' 카테고리의 다른 글
| 210708 최소 신장 트리 with Kruskal, Prim 알고리 (0) | 2021.07.10 |
|---|---|
| 210708 너비 우선 탐색(BFS) & 깊이 우선 탐색(DFS) (0) | 2021.07.09 |
| 210707 그리디 알고리즘(Greedy, 탐욕) (0) | 2021.07.08 |
| 210706 동적 계획법(DP) 2- LCS ,OBST (0) | 2021.07.07 |
| 210705 동적 계획법(Dynamic Programming, DP) (0) | 2021.07.06 |
댓글