배낭 문제 (Knapsack Problem)

배낭 문제란

배낭 문제는 제한된 용량의 배낭에 최대 가치를 가지도록 물건을 담는 문제다. 동적 계획법의 대표적인 예시로, 실생활의 자원 할당 문제를 모델링한다.

문제 유형

배당 문제는 크게 세 가지 유형으로 나뉜다:

1. 0-1 배낭 문제
2. 분할 가능한 배낭 문제
3. 무한 배낭 문제:

각 유형별 상세한 설명은 해당 페이지에서 확인할 수 있다.