[백준] No.12920 - 평범한 배낭2 (C++, Knapsack)

문제

 

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

12920번: 평범한 배낭 2

 

풀이

 

solved.ac 난이도: Platium5

 

 

[백준] 평범한 배낭(12865)의 다음 단계 문제로 같은 물건이 여러 개 있는 경우이다.

 

이 문제를 일반적인 배낭(Knapsack) 문제와 동일하게 해결하려 시간 복잡도가  O(N* K *M)이기 때문에 시간 초과가 발생한다.

따라서 다음과 같은 최적화가 필요하다.

 

물건의 개수를 2의 제곱수의 합으로 분할하는 기법을 사용한다.

만약 물건이 11개 있다면 2의 제곱수의 합으로는 다음과 같이 나타낼 수 있다.

1(2^0) + 2(2^1) + 8(2^3) = 11

 

이때 각각의 개수로 분리된 물건 A를 하나의 물건으로 생각해보자.

물건 A의 무게를 w, 만족도를 c라고 하면

A가 4개로 묶어 하나의 물건이라 생각하면 이 물건의 무게는 w*4, 만족도는 c*4가 되는 식이다.

 

단 이런 구현에는 다음과 같은 문제가 생길 수 있다.

11 이하인 2의 제곱수로 물건을 모두 분해하면 1/ 2/ 4/ 8 개의 묶음이 생기는데 모든 묶음이 모두 선택되면 1 + 2 + 4 + 8 = 15로 11을 초과한다.

 

 

따라서 다음과 같이 물건의 개수를 분할해 주었다.

for(int i=k /*물건의 개수*/; i>0 ; i >>=1){
  int part = i -(i>>1);
  divided_item.push_back({w*part, c*part});
}

 

물건의 개수가 11개라면 다음과 같이 분할된다.

1. 11 - 5 = 6

2. 5 - 2 = 3

3. 2 - 1 = 1

4. 1 - 0 = 1

 

6/ 3/ 1 /1

이 4가지 수로 1 ~ 11까지의 모든 수를 조합할 수 있고 4가지 모든 수의 합이 11을 초과하지도 않는다.

 

따라서 모든 물건을 위와 같이 분할하여주고 일반적인 knapsack알고리즘을 진행해주면 답을 구할 수 있다.

이러한 분할은 각 물건을 log(K)개로 만들 수 있기 때문에 시간복잡도는 O(N*log(K)*M)가 된다.

 

 

너무 어렵다...

이런 최적화는 어떻게 생각해 내는 걸까?

 

참조 풀이

코딩하기 좋은날 블로그 해설

 

코드