개요알고리즘 학습을 하다 보면 반드시 한 번쯤은 마주치게 되는 유명한 문제가 있습니다. 바로 '배낭 채우기 문제' (Knapsack Problem)입니다. 배낭 문제는 크게 두 가지로 나뉩니다. 물건을 부분적으로 쪼갤 수 있는 Fractional Knapsack 문제와, 물건을 온전히 하나만 선택하거나 선택하지 않아야 하는 0/1 Knapsack 문제가 있습니다. 실제 현실 세계에서는 물건을 마음대로 쪼개서 담을 수 없는 경우가 대부분이기 때문에, 0/1 배낭 문제가 주로 사용되고는 합니다. 본 글에서는 두 가지 문제 중 0/1 Knapsack 문제에 대해서 정리하고자 합니다. 배낭 문제 해결을 위한 초기 접근 방법들도둑이 보석 가게에 침입했다.배낭의 최대 용량을 초과하면 찢어지기 때문에, 무게 제한 ..
