Knapsack Problem 배낭 문제

💡 다이나믹 프로그래밍 (DP) 에서 유명한 문제
어떤 배낭이 있고 최대 무게가 K 라고 했을 때
배낭에 넣을 수 있는 N개의 물건이 각자 다른가치 V를 가지고 있고
물건마다 다른 무게 W가 있을 때,
최대한 가치가 있는 물건들을 담을 수 있는 조합을 찾는 문제

완전 탐색으로 한다면 ? (Brute Force Approach)

만약 n 개의 물건이 있을 때, 가능한 모든 조합을 만들려면 2**n 개의 경우의 수를 모두 시도해야한다

그렇기 때문에 O(2n)** 시간 복잡도가 걸리며, 좋은 접근법은 아니다

DP로 접근하기

배낭에 물건을 넣을 때, 선택 할 수 있는 경우

• 물건을 넣는다
• 넣지 않는다

무게 W	6	4	3	5
가치 V	13	8	6	12

ex) 10kg 의 배낭 = 13 V + 4Kg (10w - 6w)의 배당 최대 가치

고려해야 하는 점

1. 배낭의 최대 무게
2. 담을 수 있는 봉투의 개수 및 종류

최대 이익(dp) [i][w]

: 무게가 w 인 가방에서 i 번째 물건까지 판단했을 때 최대의 가치

과정

1. 가방 무게 초과 시
   dp[k+1][w] = dp[k][w]
2. 초과하지 않았을 때
   1. 넣지 않는다
      초과 시와 동일
   2. 넣는다
      dp[k+1][w] = K의 가치 + dp[k][w-m](현재의 무게를 뺌)

점화식

K 무게 > W 무게

dp[k][w] = dp[k-1][w]

K 무게 < W 무게

dp[k][w] = max(dp[k-1][w] , K의 가치 + dp[k-1][w-k의 무게 ]