0/1Knapsack Problem(DP)

DP(Dynamic Program, 동적계획법)을 이용하여 해결가능한 문제중 가장 기본적인 문제인 Knapsack Problem.

배낭문제의 유형으로는 0/1, bounded, unbounded, fractional 등이 있다.

 

무게와 가격이 각각 Wi, Vi,인 n개의 물건이 있습니다. 무게의 총합이 W를 초과하지 않도록 물건을 선택했을 때의 가격 총합의 최대치를 구하세요.

 

위 문제를 완전탐색을 이용하여 풀면 아래와같다.

 

각 물건 i를 선택하느냐 마느냐의 경우의 수가 존재한다.

1. i번째 물건을 배낭에 담지 않을 것이다.

2. 담을 수 있을경우 배낭에 담을 것이다.

 

int n;

int w[], v[];    //무게, 가격

 

//now부터 n -1까지 의 물건들을 용량이 capacity인 배낭에 담을때

//배낭에 담을 수 있는 최대한의 가치를 반환한다.

int ns(int now, int capacity) {

//기저사례

 if (now == n) return 0;

 

int ret = 0;

//물건을 넣을수 있다면

 if (capacity >= w[now])
  ret = max(ns(now + 1, capacity), v[now] + ns(now + 1, capacity - w[now]));

//물건을 넣을수 없다면
 else
  ret = ns(now + 1, capacity);

 return ret;
}

 

위와같은 모든 경우의 수를 직접 다 계산하는 완전탐색의 경우 0/1배낭문제에서는

O(2^n)의 시간복잡도를 갖는다. n이 30전도만 되어도 어마어마한 시간복잡도라고 볼 수있다. 대회에서 이러한 문제가 나올시 위와같은 코드로는 무조건 시간 초과가 날 가능성이 높다.

 

위 같은 문제점을 해결하기 위해 DP를 활용하자.

우선 Top-Down 방식으로 DP를 설계하면 다음과 같다.

 

1. Top-Down방식은 재귀함수를 활용한다.

2. 최적 구분 구조(Optimal Structure)를 고려하여 부분문제(Sub Problem)를 정의한다.

3. 부분문제에 대한 결과치들은 메모화(Memozation)시킨다.

4. 메모화 되어진 부분문제의 결과가 필요하다면 재귀 호출할 필요없이 메모에 써놓은     값을 참조한다.

 

int cache[MAX_NOW][MAX_CAPACITY + 1];

int ns(int now, int capacity){

  if(now == n) return 0;

 

  int &ret = cache[now][capacity];

  if(ret != -1)    return ret;

 

  ret = 0;

  if(capacity >= w[now])

    ret = max(ns(now + 1, capacity), ns(now + 1, capacity - w[now]) + v[now]);

  else

    ret = ns(now + 1, capacity);

  return ret;

}

 

다음으로 Bottom-Up방식을 이용하여 아래와 같이 문제를 해결한다.

 

1. Bottom-Up방식은 반복문for를 이용한다.

2. 점화식을 정의한다.

3. 점화식을 이용하여 원하는 결과값을 구한다.

 

dp[i][j] = 배낭의 용량이 j일경우 1~i까지의 물건을 담아 획득할 수 있는 최대가치

 

dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i])

 

int n;

int w[], v[];    //무게, 가격

int dp[MAX_N + 1][MAX_CAPCITY + 1];

 

int main(){

  //입력

    ...

  //배낭의 용량이 0인경우는 담을 수 있는 물건이 없다.

  for(int i = 0; i < n + 1; ++i)

    dp[i][0] = 0;

  //담을 물건이 없다.

  for(int i = 0; i < w + 1; ++i)

    dp[0][i] = 0;

  for(int i = 0; i < n + 1; ++i)

    for(int j = 0; j < w + 1; ++j)

      if(j >= w[i])

        dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);

      else

        dp[i][j] = dp[i - 1][j];

   cout << dp[n][w] << endl;

}

 

또다른 점화식

dp[i][j]는 i번째 이후의 무게의 총합이 j 이하가 되도록 고른 경우 최대 가치

dp[n][j] = 0

dp[i][j] = dp[i + 1][j] (j < w[i])

            max(dp[i][j - w[i]] + v[i], dp[i + 1][j]) 

이 같은 점화식으로 풀어도 원하는 결과를 얻을 수 있다.

이와 같은 dp를 이용했을때는 시간복잡도가 대략 O(nw)라고 볼 수 있다.