[배낭 문제 알고리즘]

오늘은 배낭 문제 알고리즘에 대해 알아보도록 하자

배낭 문제는 각 물건에는 가치와 무게가 존재하고, 내가 들 수 있는 정해져있을 때 최대한 많은 가치의 합을 찾는 문제이다.

쉽게 말해, 도둑 알고리즘이라고 기억하면 편하다.

---

 이 배낭 알고리즘은 대표적인 다이나믹 프로그래밍 문제 중 하나로,

1. 배낭 문제는 배낭 내 물건을 쪼갤 수 있는(일부만 선택하는) Fraction Knaspack Problem 과
2. 물건을 쪼갤 수 없는 (가져가거나 안 가져가거나)0-1 knapSack Problem으로 나눌 수있다.

이 때, 결국 모든 경우의 수를 확인해야 하므로  현재 배낭 내 물건의 최대가치와, 현재 무게 합을 고려해야하므로 2차원 배열에 담아야 한다

우선은 더 쉬운 0-1 knapSack Problem을 먼저 보도록 하자

 따라서 점화식은 DP[현재 1번 째 물건][현재 무게 합] = 현재 최대가치 로 표현해야 한다. 

0) DP[i][k] (최대 k무게까지 담을 수 있고, for 문으로 i번째 물건까지 내다봤 때, 최대 가치 ) 

if) DP[i-1][k]                                                                                         (W[i] > k) : i번째 물건 무거워서 못 담을 때

else) max( DP[i - 1][k - W[i]]   +   V[i]  ,  DP[i-1][k] )                  (W[i] <=k and i>0) : i번째 물건 담았을 때

 

대강 이해했다면 아래 백준 문제를 풀어보도록하자

https://www.acmicpc.net/problem/12865 

12865번: 평범한 배낭