(0-1) 배낭(KnapSack) 알고리즘

개념

• 배낭에 담을 수 있는 최대 용량이 있고, 각 물건들의 용량과 가치가 존재할 때 배낭에 담을 수 있는 최대 가치를 찾는 알고리즘
• 기본적으로 DP 개념 응용
• 0-1 배낭 알고리즘은 물건을 쪼갤 수 없는 상태에서의 알고리즘 풀이

2차원 DP

• 일반적인 1차원 배열의 dp가 아닌 2차원 배열로 값을 저장해야 한다.
• col은 배낭의 최대 무게, row는 n번째 물건으로 지정한다.
• 각 row, col 인덱스에 저장되는 값은 j 무게까지 담을 수 있을 때 i번째 물건을 고려했을 때 얻을 수 있는 최대 가치

DP 안에 DP

DP 문제답게 재귀성이 존재한다. 그래서 로직을 다음과 같이 바라보는 것이 중요하다고 생각한다.

최대 무게 6kg까지 수용할 수 있는 배낭에 물건을 담아 최대 가치를 찾는다.

첫 번째 물건이 3kg, 4달러라면 이 물건을 담고 최대 무게 3kg까지 수용하는 배낭에 물건을 담아 최대 가치를 찾는 문제로 생각해볼 수 있다.

이러한 논리 전개로 알고리즘을 구현한다.

수식의 경우의 수

각 물건은 배낭에 넣는다와 넣지 않는다 두 가지 경우의 수로 존재한다.

1. 넣지 않을 때

배낭의 남은 공간에 물건을 넣을 수 없거나 넣을 수 있음에도 해당 물건의 가치가 낮아 선택하지 않는 경우이다.

수식은 다음과 같다.

dp[i+1][j] = dp[i][j]

2. 넣을 때

배낭의 남은 공간에 물건을 넣을 수 있으면서 물건의 가치가 높아 넣는 선택을 한 경우이다.

식이 좀 복잡한데 수식은 다음과 같다.

dp[i+1][j] = (i+1)번째 물건의 가치 + dp[i][j무게에서 (i+1)번째 물건의 무게를 뺀 인덱스]

종합

물건을 선택해서 배낭에 넣을 때의 수식이 많이 복잡한데, 좌우지간 두 가지 경우의 수를 종합하면 dp[i][j]번째의 가치 값에 대한 수식이 다음과 같이 정리된다.

dp[i][j] = max(dp[i-1][j], i번째 물건의 가치 + dp[i-1][j - i번째 물건의 무게])

많은 도움을 받은 참고자료

수학적 사고가 많이 요구되는 알고리즘이라 글로만 설명해서는 이해가 어렵다.

훨씬 세세하게 정리해주신 글이 있으니 추가적인 개념 보충이 필요한 경우 아래글을 참고하기 바란다.

 

배낭 문제(KnapSack Problem) 그림으로 쉽게 이해하기

배낭 문제(KnapSack Problem) 그림으로 쉽게 이해하기