[Dynamic Programming] 배낭문제(Knapsack Problem)

Knapsack Problem

배낭 문제,Knapsack Problem은 다이나믹 프로그래밍에서 매우 유명한 문제이다.
용량이 K인 배낭에 넣을 수 있는 N개의 물건에 대해 각 물건의 무게 weight와 가치 value가 주어질 때, 배낭에 최대한 가치가 높은 물건들을 담을 수 있는 조합을 찾는 문제이다.
 
 

냅색 알고리즘을 나누는 기준

담을 수 있는 물건이 나뉠 수 있는가, 없는가?

 

• 담을 수 있는 물건이 나누어 질 때
  • 분할가능 배낭문제(Fractional Knapsack Problem) - Greedy
• 담을 수 있는 물건이 나누어질 수 없을 때
  • 0-1 배낭 문제(0-1 Knapsack Problem) - Dynamic Programming

 

문제 해결 전략

 

1. 모든 경우를 탐색하기(Brute Force)

N개의 물건에 대해서 담는다/안담는다의 경우가 존재하기 때문에 연산을 수행하려면 𝛩(2n ) 의 시간을 사용해야므로, 좋은 접근은 아닌 것을 알 수 있다.
 

2. 탐욕적(Greedy) 알고리즘으로 해결하기

• 0-1 배낭 채우기 문제(0-1 Knapsack Problem)
  • Greedy로 0-1냅색을 해결하는 것은 최적이 아니다!
• 분할가능 배낭 채우기 문제(Fractional Knapsack Problem) 
  • Greedy로 해결 가능하다! 물건의 일부분을 잘라서 담음으로써, 탐욕적인 방법으로 최적해를 구하는 알고리즘을 만들 수 있다.

3. Dynamic Programming

다이나믹 프로그래밍은 메모이제이션을 통해, 큰 문제를 아주 작은 문제로 쪼개서 점화식을 통해 점진적으로 해결한다.
 
다이나믹 프로그래밍(DP)기법을 적용시키기 위해서는 아래 두가지 조건이 만족되는지 살펴보아야 한다.

1. 최적 부분 구조 (Optimal substructure): 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
2. 중복되는 부분 문제 (Overlapping subproblem): 동일한 작은 문제를 반복적으로 해결한다.

배낭의 부분 문제를 적용하기 위해, 물건은 하나씩 고려하되 배낭 용량에 따른 최대 가치를 저장해나가는 방식으로 찾는다.
 
 

0-1 배낭 채우기 문제의 동적계획적인 접근방법(DP)

 
가방의 무게 만큼의 리스트 배열을 생성하고 ,짐이 하나만 존재한다면 어떻게 담을 수 있는지 해결한 후, 다음에 두 개가 존재할 때 어떻게 담을지 생각해본다.

• i>0이고 w>0일 때, 전체 무게가 w가 넘지 않도록 i번째 까지의 항목 중에서 얻어진 최고의 이익을 P[i][w]라고 하면, P[i][w]은 다음과 같이 구할 수 있다.

1. wi (현재 가방에 담을 수 있는 무게) 가 현재 물건의 무게 w보다 작거나 같을 때 (wi <= w)
   - 현재 물건을 담을 수 있다.
   - 물건을 담았을 때와 담지 않았을 때의 가치를 비교한 뒤, 더 큰 값을 할당한다.
   - 현재 물건의 가치는 v
2. wi가 현재 물건의 무게 w보다 클 때 (wi > w)
   -  현재 물건을 담을 수 없으므로, 이전 물건에서의 i에 해당하던 값 (i-1)을 넣어준다.

 
 
 
예시) P[3][30] 계산하기
 

 
 

연습 예제

 
 
Reference
https://velog.io/@jihyoun0403/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EB%B6%84%EC%84%9D-%EA%B8%B0%EB%A7%90%EA%B3%A0%EC%82%AC-%EB%8C%80%EB%B9%84-Greedy-Algorithm