냅색 - meet in the middle (밋 인 더 미들) 알고리즘

n<=40 인 n개의 정수 집합이 있다고 하자. 정수 집합의 부분집합 중 원소의 합이 S 보다 작거나 같은 부분집합 중,

그 합이 최대인 것을 구하라.

 

예제

Input : set[] = {45, 34, 4, 12, 5, 2} and S = 42

Output : 41

부분집합 {34, 5, 2}으로 41을 얻는다.

 

Input : Set[] = {3, 34, 4, 12, 5, 2} and S = 10

Output : 10

부분집합 {2, 3, 5} 으로 10을 얻는다.

 

문제를 전탐색하면 O(2^n)이다. 시간 복잡도가 너무 크다.

Meet in the middle 은 입력이 적당히 작긴 하지만 전탐색은 만만하지 않을 때 쓰는 검색 알고리즘이다.

 

 

분할 정복처럼 부분집합을 두 개로 쪼개고, 각 부분집합을 각각 풀고 병합하지만 완전히 분할 정복처럼 풀 수는 없고, 약간 변형해야 한다.

 

1. 집합을 두 부분집합으로 쪼개고, 부분집합 A, B 라고 합시다. A의 원소는 n/2 개고 B는 나머지가 들어가 있다.

2. A에서 구할 수 있는 모든 부분집합들의 원소의 합을 계산하고, 배열 X에 저장한다. 마찬가지로 B에서 구할 수 있는 모든 부분집합들의 원소의 합을 계산하고, 배열 Y에 저장한다. X와 Y 의 크기는 최대 2^(n/2) 이다.

3. X와 Y을 조합하여 합이 S보다 작은 것을 구한다.

 - 가장 간단한 방법은 X와 Y 의 모든 원소를 순회하면서 조합을 구하는 것이지만, 이것은 O(2^n)이다.

 - 시간복잡도를 줄이기 위해, Y를 정렬하고 X의 각 원소마다 순회한다. Y 에서 이진 탐색을 진행하여, x+y <= S 인 원소 y를 찾는다.

 - 이진 탐색이 시간 복잡도를 줄여 주므로 2^(n/2)log(2^(n/2)) 가 시간복잡도가 된다.

 - 계산하면 최종 시간복잡도는 O(2^(n/2) * n ) 이다.

 

// C++ program to demonstrate working of Meet in the 
// Middle algorithm for maximum subset sum problem. 
#include <bits/stdc++.h> 
using namespace std; 
typedef long long int ll; 
ll X[2000005],Y[2000005]; 

// Find all possible sum of elements of a[] and store 
// in x[] 
void calcsubarray(ll a[], ll x[], int n, int c) 
{ 
	for (int i=0; i<(1<<n); i++) 
	{ 
		ll s = 0; 
		for (int j=0; j<n; j++) 
			if (i & (1<<j)) 
				s += a[j+c]; 
		x[i] = s; 
	} 
} 

// Returns the maximum possible sum less or equal to S 
ll solveSubsetSum(ll a[], int n, ll S) 
{ 
	// Compute all subset sums of first and second 
	// halves 
	calcsubarray(a, X, n/2, 0); 
	calcsubarray(a, Y, n-n/2, n/2); 

	int size_X = 1<<(n/2); 
	int size_Y = 1<<(n-n/2); 

	// Sort Y (we need to do doing binary search in it) 
	sort(Y, Y+size_Y); 

	// To keep track of the maximum sum of a subset 
	// such that the maximum sum is less than S 
	ll max = 0; 

	// Traverse all elements of X and do Binary Search 
	// for a pair in Y with maximum sum less than S. 
	for (int i=0; i<size_X; i++) 
	{ 
		if (X[i] <= S) 
		{ 
			// lower_bound() returns the first address 
			// which has value greater than or equal to 
			// S-X[i]. 
			int p = lower_bound(Y, Y+size_Y, S-X[i]) - Y; 

			// If S-X[i] was not in array Y then decrease 
			// p by 1 
			if (p == size_Y || Y[p] != (S-X[i])) 
				p--; 

			if ((Y[p]+X[i]) > max) 
				max = Y[p]+X[i]; 
		} 
	} 
	return max; 
} 

// Driver code 
int main() 
{ 
	ll a[] = {3, 34, 4, 12, 5, 2}; 
	int n=sizeof(a)/sizeof(a[0]); 
	ll S = 10; 
	printf("Largest value smaller than or equal to given "
		"sum is %lld\n", solveSubsetSum(a,n,S)); 
	return 0; 
}

 

냅색 - meet in the middle :: 세상 끝 조그만 서가 (tistory.com)