-
알고리즘 - 배낭문제 (Knapsack Problem)study/알고리즘 2020. 2. 9. 17:32
배낭문제는 조합 최적화의 유명한 문제입니다.
한 가방에 넣을 수 있는 무게의 최대 값이 정해져 있을 때, 일정한 가치와 무게가 있는 물건들을 가치의 합이 최대가 되도록 가방에 넣는 방법을 찾는 문제입니다.
분할 가능 문제 (Fractional Knapsack Problem)
- 짐을 쪼갤 수 있는 경우
- 그리디 알고리즘(greedy method)으로 다항 시간 안에 풀이 가능하다.
0-1 배낭 문제 (0-1 Knapsack Problem)
- 짐을 쪼갤 수 없는 경우
- 동적 계획법(dp)등을 사용하여 의사 다항 시간 안에 풀이 가능하다.
- NP-완전이기 때문에 FPTAS만 존재한다.
reference - https://ko.wikipedia.org/wiki/배낭_문제
'study > 알고리즘' 카테고리의 다른 글
알고리즘 - 최대공약수(GCD)와 최소공배수(LCM) (0) 2021.02.04 알고리즘 - 다이나믹 프로그래밍 (Dynamic Programming) (0) 2020.02.10