Subset Sum: 부분집합 합
Subset Sum, 부분집합 합
정의
집합 {a_1, …, a_n} 에서 부분집합의 원소 합이 특정 값 T 가 되는 것이 존재하는가.
NP-complete in general, but pseudo-polynomial DP.
DP O(N · T)
vector<bool> dp(T + 1, false);
dp[0] = true;
for (int x : a)
for (int s = T; s >= x; s--)
dp[s] = dp[s] || dp[s - x];Meet-in-the-Middle
N ≤ 40 일 때 두 반으로 나누어 각 2^(N/2) 부분집합 합 리스트를 만든 뒤 매칭.
O(2^(N/2) · N).
응용
- Knapsack: value 있는 확장
- Balanced partition: T = SUM/2 subset sum
- Coin change
참고
이 글의 용어 (3개)
- 배낭 문제 (Knapsack)algorithm
- 정의 배낭 문제 (Knapsack Problem) 은 무게 제한 W 인 배낭에 가치 vi, 무게 wi 인 물건 N 개 중 일부를 담아 총 가치 최대화하는 조합 최적화 문제. NP…
- 비트마스크 DP (Bitmask DP)algorithm
- 정의 비트마스크 DP (Bitmask DP) 는 상태 공간이 부분집합 으로 표현될 때, 각 부분집합을 정수의 비트로 인코딩해 DP 상태로 삼는 기법. N ≤ 20 범위에서 O(2…
- SOS DP (Sum Over Subsets)algorithm
- 정의 SOS DP (Sum Over Subsets) 는 길이 2^N 의 배열 a 에 대해, 모든 mask (0..2^N-1) 마다 mask 의 부분 집합 (submask) 에 대…
💬 댓글