배낭 문제(Knapsack Problem)는 조합 최적화(combinatorial optimization) 문제로, 제한된 용량의 배낭에 최대 가치를 가지는 물건들을 선택하는 문제이다. 이 문제는 주어지는 물건들이 각각의 무게와 가치로 표현되며, 배낭의 총 용량을 초과하지 않도록 물건을 선택해야 한다. 배낭 문제는 다양한 변형이 있으며, 그 중 가장 일반적으로 알려진 두 가지 변형은 0-1 배낭 문제와 분수 배낭 문제이다.

0-1 배낭 문제에서는 각각의 물건을 선택할 수 있는 선택지가 "선택" 혹은 "미선택"의 두 가지로 제한된다. 즉, 각 물건은 배낭에 한 번만 담을 수 있다. 이 문제는 NP-완전(NP-complete) 문제로 간주되어, 최적의 해를 찾기 위한 효율적인 알고리즘이 알려져 있지 않다. 따라서 일반적으로 동적 프로그래밍(dynamic programming)이나 분기 한정법(branch and bound)과 같은 알고리즘이 사용된다.

분수 배낭 문제는 물건을 선택할 때 일부를 선택할 수 있는 경우를 다룬다. 이 경우, 물건은 연속적으로 분할이 가능하며, 각 물건의 무게와 가치는 비례적으로 적용된다. 분수 배낭 문제는 그리디 알고리즘(greedy algorithm)을 사용하여 효율적으로 해결할 수 있으며, 최적 해를 보장한다.

배낭 문제는 재무 관리, 물류, 자원 배분 등 다양한 실제 문제에 적용될 수 있다. 또한, 알고리즘과 데이터 구조를 배우는 학생들에게 자주 사용되는 기본적인 문제로, 최적화 기술을 이해하는 데 중요한 역할을 한다.