백준 7579번 앱

백준 7579번 링크

Knapsack problem

Optimization version

NP hard 문제이다. Optimization version의 정의는 다음과 같다.

Input: Positive integers $W, w_{1}, ... , w_{n}$ and $v_{1}, ... , v_{n}$
Output: A subset S $\subset$ {1, ... , n} that maximizes $\Sigma_{i\in S}v_{i}$ subject to $\Sigma_{i\in S}w_{i} \le W$

쉽게 말하면 n개의 배낭이 있고, 각 배낭은 가격과 가치가 있다. 한정된 돈으로 최대한의 가치를 얻는 방법을 묻는 문제다. weight와 value라고 표현하는 게 개인적으로 편한 것 같다.

Deicision version

이 문제가 NP hard인 것을 증명하기 위해서는 decision version이 NP-complete라는 것을 증명하면 된다. decision version은 다음과 같다.

Input: Positive integers $W, w_{1}, ... , w_{n}$ and $V, v_{1}, ... , v_{n}$
Output: Is there a subset S $\subset$ {1, ... , n} s.t. $\Sigma_{i\in S}v_{i} \ge V$ subject to $\Sigma_{i\in S}w_{i} \le W$ ?

subset sum problem을 knapsack (decision)으로 reduce하면 된다. 꽤나 간단하게 reduction이 가능하다.

subset sum problem의 input ${a_{1}, ... , a_{n}}$, $T$ (target sum)이 존재한다. $w_{i} = a_{i}, v_{i} = a_{i}$, for $\forall{i}, W = T, V = T$로 두면 간단하게 끝이다. subset sum은 입력이 unary가 아닌 이상 NP-complete이므로, knapsack (decision)도 NP-complete라는 것을 알 수 있다.

문제 풀이

다시 백준 문제로 돌아가보자. 위에서 정의한 것과 약간 다르다. Target value가 입력으로 주어지고, 최소의 비용을 정답으로 출력해야 한다. knapsack은 DP를 이용해 해결할 수 있다. (물론 DP로 해결된다는 것이 P에 속한다는 뜻은 아니다.)

아이디어

DP[n][n * v_max]

j번째부터 n-1번째 원소만 사용한다. 해당 원소들만 사용하여 subset을 만드는데, 정확히 k만큼의 weight를 가지는 subset이 있다면 value의 총합이 DP[j][k]가 된다. 그런 subset이 없는 경우, 0으로 한다. v_max는 value 중 가장 큰 값이다.

문제에서 최대 개수는 100, 최대 비용도 100이므로 subset의 최대 비용은 10000이다. 따라서 배열은 [100][10001]으로 선언한다.

초기화

Top row부터 내려오는 방식을 사용한다.

DP[n][i]

$v_{i} = i$인 경우 $w_{i}$로 초기화하고, 아닌 경우는 0으로 초기화한다.

점화식

DP[i][k] = min(DP[i + 1][k], DP[i + 1][k - w[i]] + v[i])

DP[i][k]는 i번째 원소부터 사용하여 비용이 k인 subset 중 최대의 value 값이다. 따라서 i+1번째 원소부터 사용하여 비용이 k인 경우, 또는 i+1번째 원소부터 사용하여 비용이 k - w[i]인 집합을 만든 경우를 비교해야 한다.

결과

0번째 row를 search하여 value가 우리가 원하는 값 이상인 것 중 비용이 최소인 경우를 찾는다.

시간 복잡도

O($n^{2} *v_{max}$)

Polynomial time?

Polynomial time처럼 보일 수 있지만, 아니다. 만약 맞다면 knapsack (decision)이 P이면서 NP-complete이므로 P=NP를 증명한 셈이다.

왜 아닐까? 위에서 subset sum의 입력이 unary가 아닌 이상 NP-complete라고 한 것과 이유가 같다. 입력이 binary인 경우, v_max가 exponential하게 커질 수 있기 때문이다.

예를 들면 이해가 훨씬 쉬워진다. 각 $w_{i}, v_{i}$가 b개의 bit로 이루어진다고 가정해보자. 총 입력의 길이를 l이라 하면 2bn = l이다. (계산의 편의를 위해 $W, V$는 잠시 무시하겠다) b = n인 경우, b = n = $\sqrt(l/2)$이다. 이 경우, 시간 복잡도는 O($(l/2)^2*2^{\sqrt(l/2)}$)로, NP에 속한다.

디버깅

배열을 [100][10000]로 선언했는데, 0부터 10000의 크기이므로 10001이어야 한다.

코드

#include <iostream>

using namespace std;

int v[100];
int w[100];
int V;
int n;

/* [j][k] : use j-th ~ n-1th. 
if a subset whose weight is exactly k, DP[j][k] is the value of it
else, infinite */
int DP[101][10001];

int main(void) {
	cin >> n >> V;

	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}

	for (int i = 0; i < n; i++) {
		cin >> w[i];
	}

	for (int i = 0; i <= 100 * n; i++) {
		if (w[n - 1] == i) {
			DP[n - 1][i] = v[n - 1];
		}
		else {
			DP[n - 1][i] = 0;
		}
	}

	for (int r = n - 2; r >= 0; r--) {
		for (int c = 0; c <= 100 * n; c++) {
			if (c >= w[r]) {
				DP[r][c] = max(DP[r + 1][c], DP[r + 1][c - w[r]] + v[r]);
			}
			else {
				DP[r][c] = DP[r + 1][c];
			}
		}
	}

	for (int i = 0; i <= 100 * n; i++) {
		if (DP[0][i] >= V) {
			cout << i << endl;
			break;
		}
	}

	return 0;
}