배낭 문제 - Knapsack Problem

📌 배낭 문제란?

배낭문제 , 냅색 문제 - $Knapscak$ $Problem$

📌 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 방법이 무엇인가?

가방의 무게가 주어졌을때 물건들을 적절히 골라서 가치의 최대값을 구하는 문제이다.

위 사진에서 최적의 조합은 초록색 상자를 제외한 나머지 물건을 다 가져가면
8kg 으로 총 15$의 가치를 얻을수 있다.

배낭문제는 다이나믹 프로그래밍을 활용한 문제이다. 배낭문제 이외에도 LCS , LIS 알고리즘 또한 존재한다.

📌 배낭문제 점화식

• $dp[i][j]=max(dp[i-1][j-weight]+value , dp[i-1][j])$

물건의 무게는 $weight$ 이고 가치는 $value$ 일때

$dp$ 배열의 $x$ 축은 물건의 무게를 구하고 $y$ 축은 물건의 종류를 고려한다.

$dp[i-1][j-weight]+value$ 는 이전값에서 물건을 챙겼을때
$dp[i-1][j]$ 는 물건을 챙기지 않았을때를 의미한다.

📌 배낭문제 시간복잡도

원래라면 모든 물건에 따른 모든 경우의 수를 구할려면 각각의 물건마다 아이템을 넣거나 넣지않거나 둘중 하나를 저장해야 하기 때문에 $O(2^N)$ 의 시간 복잡도가 필요하지만

배낭문제 알고리즘을 사용하면 시간복잡도는 $O(N^2)$ 으로 풀수 있다.

📌 점화식에 대하여

배낭문제 알고리즘은 보통 최대값이나 최소값 , 경우의 수를 구하지만
문제마다 언제든지 변형 가능하기 때문에 사실 위에 써놓은 점화식이 절대적이지 않다.
점화식은 문제에 따라 언제든지 변형해서 써야하며 적절하게 바꿔써야한다.

처음 점화식을 만들고 짤려고 하면 매우 어렵지만 문제에서 구하고자 하는것을 명확히 하는것이 제일 중요하다.

$dp$ 배열의 $x$축과 $y$축이 각각 무엇을 의미할지 , 무엇을 구할 것인지를 고려해야한다.

가장 기초적인 배낭문제인 평범한 배낭 문제는 dp[i][j]가 있을때 i번째 아이템까지 고려했을때와 j번째 비용의 최대값을 구하는것을 목표로 한다.

다른사람들의 블로그에서 $dp$ 테이블의 변화를 잘 정리한 글이 많으니 그것을 보며 이해하는것이 좋다.

배낭문제 문제집 이 문제집을 통해서 배낭문제에 대한 감각을 찾는것을 추천한다.

배낭문제애 대해 처음배울땐 여러가지 문제를 접하면서 점화식이 평범한 배낭에서 사용했던 점화식에서 어떻게 변형되는지 이해하고 왜 그렇게 변형되었는지 이해한다면 나중에는 스스로 점화식을 세울 수 있을것이다.