배낭 문제: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Juniuswikiae (토론 | 기여) 편집 요약 없음 |
|||
8번째 줄:
짐을 쪼갤 수 없는 경우의 배낭문제를 '''0-1 배낭문제'''(0-1 {{lang|en|Knapsack Problem}})라 부른다.
이 문제는 쪼갤 수 있는 경우에는 [[그리디 알고리즘]]으로 [[다항 시간]]에, 쪼갤 수 없는 경우에는 [[동적계획법]](Dynamic Programming)등으로 [[의사 다항 시간]]에 풀 수 있다. 단, 쪼갤 수 없는 경우는 [[NP-완전]]이기 때문에 알려진 다항 시간 알고리즘은 없고, [[다항 시간 근사 해법|FPTAS]]만 존재한다. 배낭 문제에 대한 FPTAS는 [[오스카 이바라]]와 [[김철언]]이 [[1975년]]에 개발하였다. <ref>Oscar H. Ibarra and Chul E. Kim, Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems, Journal of the ACM (JACM), vol. 22, no. 4, 1975</ref>
== 참고문헌 ==
| |||