[백준/BOJ] 12920 평범한 배낭 2★- 접근과 풀이 (c++)

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

12920번: 평범한 배낭 2

알고리즘 복습하던 중 배낭문제를 푸는 방법이 희미해져서 찾아서 푼 배낭문제. 

0-1 Knapsack은 그리디가 정해지만,  Fractional Knapsack 문제는 푸는 방법이 다양하다.

난 그중에서도 dp를 사랑하므로 dp로 접근했는데, 상당히 어려운 문제였다..

 

---

접근 방법

 

배낭문제의 기본형인 12865번 문제 - 평범한 배낭 과 비슷하게 접근하였다. 

배낭문제에서 dp로 풀때 점화식을 아래처럼 세운다.

 

dp[idx][cap] = idx번째까지 물건을 넣은 배낭의 용량이 cap일때, 남은 물건을 최대로 넣는 경우

 

이 문제도 마찬가지로 하되, idx+1 번째의 물건을 넣을 때 물건의 개수인 K만큼 반복문을 돌려주면 될 줄 알았으나,  O(NMK)의 시간복잡도로 당당히 TLE를 받았다.

 

 

도저히 답이 안나와서 풀이를 찾아보았는데, 물건의 개수를 2의 거듭제곱으로 분할하여 나타내는 것이 핵심이었다.

 

15개의 물건이 있으면 1,2,4,8개의 물건으로 분할하여 각각 4개의 물건으로 생각하면 1~15까지의 개수를 모두 나타낼 수 있는 것이다. 

 

그러나 11개와 같은 경우, 1,2,4,8개로 분할하면 12~15개의 물건은 불필요해지는데, 이와같은 경우를 처리하는 부분에 대해서 설명이 잘 되어있는 블로그가 없었다. 

11은 1 / 1 / 3 / 6 으로 나눈다는데 어떤 방식으로 나누어지는지 알 수가 없었다. 

 

 

그래서 떠올린 부분이, K보다 작으면서 가장 큰 거듭제곱수까지 분할하고, 남은 개수까지 포함하기로 했다.

 

예시를 들자면, 100개의 물건을 분할할 때, 1, 2, 4, 8, 16, 32개로 나누면 1 ~ 63까지의 개수를 커버할 수 있다.

그리고 남은 37개를 한 묶음으로 둔다면 1 ~ 100까지의 수를 모두 나타낼 수 있고, 이는 log K +1 개 이므로 O(NM logK)의 시간 복잡도로 문제를 해결할 수 있다. 

 

그리고 모든 물건을 이처럼 분할하고 나면 일반적인 배낭문제와 같이 풀면 된다. 

 

dp배열의 [idx] 크기를 지정할 때, 100종류의 물건이 있지만 최대로 분할하면 log(10000) = 14.xxx 이므로 1400이상으로 설정하여야 한다.

 

추가로, dp[idx][cap] =  idx까지 용량이 cap... 으로 선언하니 solve 함수에서 벡터의 인덱스가 idx+1이 되다보니 벡터의 마지막 메모리를 침범하여 이상한 값이 나와서 조금 헤맸다..

 

---

풀이

 

tag : knapsack, dp

 

#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
int N, M;
vector<int> weight, price;
int dp[3010][10001]={0};
int solve(int idx, int cap){
  //idx번째부터 담는다. 용량은 현재 용량은 cap
  if(idx==weight.size())
    return 0;
  int &ret = dp[idx][cap];
  if(ret!=-1)
    return ret;
   ret =  solve(idx + 1, cap); //못담음
  if(M-cap >= weight[idx] ) //담을수있음
    ret = max(ret,solve(idx + 1, cap + weight[idx] )+ price[idx]);
  
  return ret;
}
int main(){

  cin >> N >> M;
  for (int i = 1; i <= N;i++){
    int w, p, cnt;
    cin >> w >> p >> cnt;
    
    int bin = 1;
    while(bin*2 - 1<=cnt){
      weight.push_back(bin * w);
      price.push_back(bin * p);
      bin *= 2;
    }
    if(bin-1!=cnt){
      weight.push_back((cnt- (bin-1))*w);
      price.push_back((cnt- (bin-1))*p);
    }
  }
  memset(dp, -1, sizeof(dp));
  cout << solve(0, 0);

}