[Algorithm/BOJ] KnapSack _ DP

knapsack problem : 배낭 문제 

용량이 m인 가방이 하나 주어졌을 때, 각각 가치와 무게가 정해진 n개의 물건들에 대하여  합이 m 이하이고 가치의 합이 최대가 될 수 있는 물건 부분집합을 구하는 문제이다.

배낭문제는 fractional knapsack or 0-1 knapsack 두가지가 있다. 
후자는 물건을 쪼갤 수 없다고 가정하는 알고리즘으로, 지금 다루어 볼 것이다. 

 

 

<BOJ/12865:평범한 배낭>

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

12865번: 평범한 배낭

위의 문제는  knapsack 문제이다. 
이 문제를 모든 경우를 가지치기 해나가면서 백트레킹으로 해결하려 든다면 2**n의 시간 복잡도가 발생할 것이다. 따라서 물건의 수 n이 커질 수록 시간복잡도가 급속도로 증가하는 양상을 띄게 될 것이다. 

 

M = 7, n=4
Vi = (13,8,6,12) , Wi = (4,6,4,3,5)

 

KnapSack 문제는 대표적으로 dp를 이용해 해결할 수 있다.  먼저 problem 을 sub problem들로 나누어 보자. 
나누는 과정에서 주의해야할 부분은 물건이 무조건 들어가지 않는 경우도 고려를 해 주어야 한다는 것이다. 

 

위와 같은 경우는 각 물건(원소)가 포함되는 경우만을 고려한 것이고  각 원소가 포함되지 않은 경우는 고려되지 않은 것이다.	원소가 포함되지 않는 경우와 포함되는 경우 모두 고려한 것 따라서 이 그래프가 옳은 것이다.

두번째 그림을 함수로 표현하면 아래와 같다. 
f(n,w) = max(f(n-1,w)+0, f(n-1,w-w[n])+val[n])

f(n번째 i 까지 탐색, 한계무게)

함수를 보면 알 수 있듯이 전달되는 인자가 2개이므로 이차원 배열을 이용하여 구현할 수 있다. 

 

dp식 자체가 이중 포문으로 위의 표를 돌아야 하기 떄문에 시간 복잡도는 o(n*w)가 될 것이다. 

#include <iostream> #include <algorithm> #include <vector> #include <cmath> using namespace std; int n, k; // 물품의 수, 버틸 수 있는 무게 int main(){     cin>>n>>k;     int dp[105][100005]; // value의 합 저장     int w[105]; int val[1005]; // 각 물건의 무게, 가치 저장     int result = 0 ; // 최대 가치 저장     for(int i=1; i<=n; i++){         cin>>w[i]>>val[i];     }     for(int i=1; i<=n ; i++)     {         for(int j=0; j<=k; j++){             if(w[i]<=j) { // 물건i 의 무게가 한계 무게치보다 큰 경우, 물건i를 가방에 넣을 수 없으므로 0                 dp[i][j]=max(dp[i-1][j]+0,dp[i-1][j-w[i]]+val[i]); // 한계 무게보다 작은 경우, 물건i의 가치를 더하는 것과 더하지 않는 것중 유리한 것을 택한다.             }else dp[i][j] = dp[i-1][j] ;             result = max(result,dp[i][j]); // 최대 가치 저장         }     } //    cout<<result<<endl; //    for(int i=0; i<=n; i++){ //        for(int j=0; j<=k; j++){ //            cout<<dp[i][j]<<" "; //        } //        cout<<"\n"; //    }     return 0; }