Subset Sum Problem

0-1 Knapsack Problem 에 대한 고찰

 

 

이전에 0-1 Knapsack Problem에 대해서 Input 을 고려할 때, 물건의 갯수 n과 최대로 챙겨오기 위한

무게 W에 대해서 시간복잡도가 O(nW) 가 나왔다.

 

이는 Polynoimal time algorithm 즉, "P에 속한 알고리즘일까?" 라는 생각을 해봐야 한다.

 

이전에 했던걸 예로 들면 n = 6, W = 10이므로 n * W = 60 번만에 최대 이익을 낼 수 있었다.

 

그렇다면 다음과 같은 극적인 상황을 고려해보자.

 

 

 

Profit은 고려하지 말고 weight만 살펴보도록 하자.

 

80M 즉, 8 * 10^7 의 weight 을 가지고 있으며 최대로 챙겨올 수 있는 무게가 만약 100M 이라고 한다면

W = 10^8, 즉 6개의 option이 존재하므로 6 * 10^8 = 6억번의 연산을 실행해야만 최대 이익을 구할 수 있다.

 

이는 정말 효율적인 알고리즘일까?

 

6개의 option 임에도 불구하고 6억번의 연산을 함으로써 엄청난 시간을 낭비하고 있다.

 

정리하자면, W = 2^n 이라고 주어진다면 ...

O(n * W) = O(n * 2^n), 결국 Polynomial time algorithm 이 아니라는 것을 알 수 있다.

 

 

아무도 0-1 Knapsack prolem에 대해서 polynomial time algorithm 을 찾지도 증명도 못했다고 한다.

 

즉, 이러한 문제를 NP-complete 라고 부른다.

 

 

A Variation of the 0-1 Knapsack Problem

 

 

※ Problem

Given n items of length l1, l2, ..., ln, is theree a subset of these items with total length exactly L?

 

... 약간의 변형 문제이다.

 

Profit은 주어지지 않았지만 Length(weigth)만을 활용하여 정확하게 주어진 Length를 뽑아내야 한다.

 

예시를 들어보자.

 

{ 1, 2, 7, 14, 49, 98, 343, 686, 2409, 2793, 16808, 17206, 117705, 117993 }, L = 138457

       → {1, 2, 7, 98, 343, 686, 2409, 17206, 117705}

 

 

① A Divide-and-Conquer Approach

 

다음과 같은 recursive한 함수 fill(i, j)에 대해서 보도록 하자.

 

먼저 fill(i, j) 는 2가지 경우에 대해서 TRUE를 반환한다.

 

① i번째 item이 사용된다면, fill(i - 1, j - l[i]) 는 TRUE 를 반환한다.
② i번째 item이 사용되지 않는다면, fill(i - 1, j) 는 TRUE 를 반환한다. 

 

그러면 fill(i, j) 에 대한 code 를 살펴보도록 한다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int l[14] = { 1, 2, 7, 14, 49, 98, 343, 686, 2409, 2793, 16808, 17206, 117705, 117993 };
int L = 138457, cnt;

bool fill(int i, int j) {
	cnt++; // counting variable
	if (i == 0) {
		if (j == 0) return true;
		return false;
	}
	if (fill(i - 1, j))
		return true;
	else if (l[i] <= j)
		return fill(i - 1, j - l[i]);
}

int main()
{
	if (fill(13, L))
		printf("YES!");
	else
		printf("NO!");
	printf(" => %d", cnt);

	return 0;
}

 

 

 

거대한 숫자가 나왔다. 적어도 n^2 을 넘어선 숫자가 나온것을 알 수 있겠다.

 

왜 이렇게 많은 재귀 호출이 일어났을까?

 

재귀적으로 (i - 1, j)에 대한 fill 함수를 호출하고 false일 경우에 추가적으로 (i - 1, j - l[i]) 에 대한 fill 함수를

호출한다.

 

이때 l[i] = 1 이라고 가정하고 다음과 같은 상황을 단순하게 생각해보도록 하자.

 

 

false가 떠서 파란색 화살표로 이동하는 것을 알 수 있다.

 

이 때, 색칠되어진 (i - 2, j - 1) 부분이 (i - 1, j - 1) 에서 올 수 있고 (i - 1, j) 에서 올 수도 있다.

 

즉, overlapping subprogram이 생긴다는 건데 이로 인해서 n^2 이 넘어선 숫자가 출력된 것을 알 수 있겠다.

 

 

 

② A Dynamic Programming Approach

 

다이나믹 프로그래밍 기법으로 O(nL) 에 대한 구현이 가능하다.

 

먼저 Optimal substructure 를 생각해보도록 하자.

 

 

(1) i번째 길이를 포함하지 않은 경우 정확하게 j값을 만들 수 있어야 한다.

      즉, fill(i, j) = fill(i - 1, j) 임을 알 수 있다.

 

(2) (1)의 경우가 false 라면, i번째 길이를 포함하여 정확하게 j 값을 만들 수 있어야 한다. 

       즉, fill(i, j) = fill(i - 1, j - l[i]) 이다. (이때 j >= l[i])

 

 

 

 

 

O(nL) - time 에 대한 code는 다음과 같다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int l[7] = { 1, 2, 2, 4, 5, 2, 4 };
int L = 15;
bool F[8][16];

void show_table(int n, int L) {
	int i, j;
	for (i = 0; i <= n; i++) {
		for (j = 0; j <= L; j++) {
			if (F[i][j]) printf("T ");
			else printf("F ");
		}
		printf("\n");
	}
}

bool fill(int n, int L) 
{
	int ll, i;
	F[0][0] = true;
	for (ll = 1; ll <= L; ll++) F[0][ll] = false;
	for (i = 1; i <= n; i++) {
		for (ll = 0; ll <= L; ll++) {
			F[i][ll] = F[i - 1][ll];
			if (!F[i][ll] && ll - l[i - 1] >= 0)
				F[i][ll] = F[i - 1][ll - l[i - 1]];
		}
	}

	show_table(n, L);

	return F[n][L];
}

int main()
{
	if (fill(7, L))
		printf("YES!");
	else
		printf("NO!");

	return 0;
}

 

 

 

Subset Sum

 

 

※ Problem

Given a set of positive integers {w1, w2, ..., wn} of size n and a positive integer W,

find a subset A of {1, 2, ..., n} that maximizes  Σi∈A (wi) subject to  Σi∈A (wi) ≤ W.

 

subset sum 문제를 0-1 knapsack 문제를 이용해서 어떻게 해결해야 할까?

 

 

 

 

사실 subset 문제에 profit에 대한 transform 을 처리해준다면 0-1 knapsack 문제가 되버린다.

 

{p1, p2, ..., pn} = {w1, w2, ..., wn} 에 대한 변환을 해준다면 0-1 knapsack 문제가 되고 기존에 풀었던

방법 그대로 하여 해당 문제를 해결할 수 있다.

 

 이 문제 또한 0-1 Knapsack 문제처럼 NP-complete으로 polynomial time에 해결할 수 없는 문제이다. 

 

P_SS <= pP_Knap 으로 subset 문제를 0-1 knapsack으로 변환하는 것은O(n)의 transform이 

가능하고 이를 polynomial reduction 이라 함