Knapsack Problem Definition in Wikipedia 배낭 문제 ( Knapsack Problem 냅색 프라블럼 [ * ] )는 조합 최적화 의 유명한 문제이다. 간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 이 배낭문제는 짐을 쪼갤 수 있는 경우(무게가 소수 일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0 이상의 정수만 가능) 두 가지로 나눌 수 있는데, 짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제 ( Fractional Knapsack Problem ), 짐을 쪼갤 수 없는 경우의 배낭문제를 0-1 배낭문제 (0-1 Knapsack Problem )라 부른다. 이 문제는 쪼갤 수 있는 경우에는 그리디 알고리즘 으로 다항 시간 에, 쪼갤 수 없는 경우에는 동적계획법 (Dynamic Programming)등으로 의사 다항 시간 에 풀 수 있다. 단, 쪼갤 수 없는 경우는 NP-완전 이기 때문에 알려진 다항 시간 알고리즘은 없고, FPTAS 만 존재한다. 배낭 문제에 대한 FPTAS는 오스카 이바라 와 김철언 이 1975년 에 개발하였다. ZeroDivision Error https://airbrake.io/blog/python-exception-handling/zerodivisionerror-2 Greedy metrics