배낭 알고리즘이란? 배낭 문제(Knapsack)는 n개의 물건과 배낭 있을 때, 각 물건에는 가치와 무게가 존재한다. 또한 각 물건은 1개씩만 있다. 배낭에는 담을 수 있는 최대 용량이 존재한다. 이러한 조건일 때, 배낭의 최대 용량을 초과하지 않으면서 배낭에 담을 수 있는 최대 가치의 합을 찾는 문제이다. 해당 그림은 배낭 문제의 예시이다. 지금부터 알고리즘을 설명할 때 해당 예시를 가지고 계속 설명하겠다. 0-1 KnapSack Problem 배낭 문제는 물건을 쪼갤 수 있는 Fraction Knaspack Problem과 물건을 쪼갤 수 없는 0-1 knapSack Problem으로 나뉜다. 이 글에서 설명하고자 하는 것은 0-1 KanpSack Problem이다. 대표적인 DP(Dynamic Pr..