knapsack.md

배낭 문제 (knapsack problem, 냅색 문제)

• 조합 최적화 문제의 일종
• 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게, 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분집합을 찾는 문제
• 배낭 문제는 분할 가능한 배낭 문제, 0-1 배낭 문제가 있다.
• cf. 나무 위키 - 배낭 문제

분할 가능한 배낭 문제 (fractional knapsack problem)

• 그리디 알고리즘으로 풀 수 있다.

0-1 배낭 문제

• 그리디 알고리즘으로 최적해를 찾을 수 없다.
• 동적 계획법, 백트래킹 등의 조합 최적화 문제의 풀이법으로 풀어야 한다.