Knapsack Problem(배낭 문제)

오늘은 배낭 문제(Knapsack Problem, 냅색 프라블럼) 에 대해 배워보겠습니다. 

배낭 문제는 조합 최적화의 유명한 문제 입니다. 

 

:도둑이 다른 가치와 다른 무게가 있는 보석을 훔치는데 넣을 수 있는 무게가 정해진 가방에 최대한 많이 넣는 문제입니다.

 

이 배낭문제는 짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제(Fractional Knapsack Problem) 과 짐을 쪼갤 수 없는 경우 0-1 배낭문제(0-1 Knapsack Problem) 라 부릅니다.   

 

저희 분할 가능 배낭문제를 그리디 관점에서 살펴보도록 하겠습니다. (다항시간에 풀 수 있습니다. 0-1 배낭문제는 DP로 풀 수 있습니다.)

 

훔친 물건 중에 가치가 가장 높은 거 부터 넣습니다. 그리디는 쉽게 생각할 수 있지만 항상 최고의 해답을 내는 것은 아닙니다. 아직 아무도 exponential 보다 나은 알고리즘은 만들진 못했습니다.