내용
-
Subset Sum 문제는, positive integer multiset S와 정수 t가 주어졌을 때, 합이 t인 S의 부분집합이 있는지를 찾는 문제이다.
-
S의 원소 범위가 1 이상 M 이하의 정수라고 가정하자. M 에 대한 dependency가 없이 풀려면 당연히 NP-hard이다.
-
그냥 DP를 하면 O(n2M) 이다.
-
각 숫자를 prefix sum으로 처리하면 O(nM2)이다.
-
Generating function으로 O(nMlognM) 에 푸는 풀이가 비교적 최근에 발견되었다.
-
꽤 깔끔한 O(nM) 풀이를 서술
-
일단 첫 번째 Lemma는, 이 문제를 모든 수가 [-M, M] 인 multiset S에서 합이 1 ⇐ t ⇐ M 이 되는 subset을 찾는 문제로 변형할 수 있음
-
이건 쉽게 보일 수가 있는데, 합이 t가 될 때까지 greedy하게 아무거나 고르면 됨
-
그래서 합을 정말 t로 만들었으면 잘 된거고
-
아니면 t - 1 이하의 무언가일텐데, 만약에 t-M 이하면 고를 게 없었다는 뜻이니까 실패한거고
-
아니면 고른 것에 음수, 안 고른 것에 양수 취한다음에, t - (지금 고른 집합) 을 목표로 하는 subset을 찾으면 됨
-
음수 (고른 것) 들을 {a_1, a_2, \ldots, a_n} 양수 (안 고른 것) 들을 {b_1, b_2, \ldots, b_m} 라고 하면 (a_i < 0 < b_i)
-
여기서 합이 1 ⇐ t < M 인 걸 양쪽에서 고르는 문제
-
DP[i][j][k] 를 a[1..i] b[1..j] 에서 합이 k인걸 고를 수 있는지를 저장하는 boolean 테이블이라고 하면
-
여기서 1 ⇐ k ⇐ 2M 인 것만 봐도 됨.
-
왜냐? 0 이하로 내려갈정도로 마이너스를 너무 많이 먹었으면 어차피 플러스를 먹어야 하니까 j를 늘려서 플러스를 먹어서 올리고 2M 초과일때도 i를 늘려서 마이너스를 먹어서 줄일 수 있으니까
-
이때 복잡도는 O(n2M)
-
이제 여기서 상태 바꾸는 트릭을 사용. DP[i][j][k] → DP[i + 1][j][k] 이니까, F[j][k] = (DP[i][j][k]가 참인 최소 i) 라고 정의
-
그리고 이제 DP의 상태 전이는 전부 부등식으로 나오는데
- F[j][k] >= F[j + 1][k]
- F[j][k] >= F[j + 1][k + b[j]]
- For all i >= F[j][k], i + 1 >= F[j][k + a[i]]
-
다 좋은데 마지막 항이 불편
-
근데 여기서 F[j][k] >= F[j + 1][k] 라는 항에 주목하면
-
F[j - 1][k] >= F[j][k] 니까 내가 이걸 j가 증가하는 순서대로 채워나갔다. 라고 하면
-
For all i >= F[j - 1][k], i + 1 >= F[j - 1][k + a[i]] >= F[j][k + a[i]] 이라는 것이 앞 단에서 이미 다 보존됨
-
그래서 저 루프를 F[j - 1][k] … N 에 대해서 다 돌리는 건 낭비이고 F[j - 1][k] > i >= F[j][k] 에 대해서만 돌리면 됨
-
그러면 투 포인터랑 동일한 이유로 Amortized O(nM)
-
그래서 가중치 (M) 혹은 무게 (W)가 constant bounded된 subset sum / knapsack 문제는
- subset sum: O(n^2M) (naive), O(nM^2) (prefix sum) O(nM) (pisinger99)
- knapsack: O(n^2M) (naive), O(nMW) (pisinger99), O(nM^2) (https://www.acmicpc.net/problem/13058 + SMAWK = https://arxiv.org/pdf/1802.06440.pdf)
출처: https://koosaga.com/288 [구사과:티스토리] 출처: https://koosaga.com/288 [구사과:티스토리]