NP hard 문제이다. Optimization version의 정의는 다음과 같다.
Input: Positive integers and
Output: A subset S {1, ... , n} that maximizes subject to
쉽게 말하면 n개의 배낭이 있고, 각 배낭은 가격과 가치가 있다. 한정된 돈으로 최대한의 가치를 얻는 방법을 묻는 문제다. weight와 value라고 표현하는 게 개인적으로 편한 것 같다.
이 문제가 NP hard인 것을 증명하기 위해서는 decision version이 NP-complete라는 것을 증명하면 된다. decision version은 다음과 같다.
Input: Positive integers and
Output: Is there a subset S {1, ... , n} s.t. subject to ?
subset sum problem을 knapsack (decision)으로 reduce하면 된다. 꽤나 간단하게 reduction이 가능하다.
subset sum problem의 input , (target sum)이 존재한다. , for 로 두면 간단하게 끝이다. 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]
인 경우 로 초기화하고, 아닌 경우는 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()
Polynomial time처럼 보일 수 있지만, 아니다. 만약 맞다면 knapsack (decision)이 P이면서 NP-complete이므로 P=NP를 증명한 셈이다.
왜 아닐까? 위에서 subset sum의 입력이 unary가 아닌 이상 NP-complete라고 한 것과 이유가 같다. 입력이 binary인 경우, v_max가 exponential하게 커질 수 있기 때문이다.
예를 들면 이해가 훨씬 쉬워진다. 각 가 b개의 bit로 이루어진다고 가정해보자. 총 입력의 길이를 l이라 하면 2bn = l이다. (계산의 편의를 위해 는 잠시 무시하겠다) b = n인 경우, b = n = 이다. 이 경우, 시간 복잡도는 O()로, 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;
}