부분집합 점화식

Q. n개의 숫자로 이루어진 집합 S에 대해, 집합의 숫자를 묶어서 각 묶음의 숫자 합이 x이하가 되도록 하는 최소 묶음의 수를 구해라.

A.
점화식

f\left(s\right)\ =\ f\left(s\ \setminus \ p\right)\ \ \text{for}\ \ m\left(s\ \setminus \ p\right)\ +\ a\left[p\right]\ \le \ x

m(s) 는 집합 s의 묶음 중 합이 최소인 묶음의 합이다. 또한 F(p, 0, n)을 진행하면서 추가로 들어오는 원소를 모두 고려하기 때문에 inner for문의 작업이 끝났을 때는 m(s)에 합이 최소인 묶음의 합이 들어감이 보장되어있다.

F(s, 1, 1 << n) {
    memo[s] = {n+1, 0};
    F(p, 0, n) if (s & (1 << p)) {
        auto sub = memo[s ^ (1 << p)];
        if (sub.second + a[p] <= x) {
            memo[s] = min(memo[s], {sub.first, sub.second + a[p]});
        } else {
            memo[s] = min(memo[s], {sub.first+1, a[p]});
        }
    }
}

챙겨가면 편한 비트마스킹 성질 :

0부터 1<<n 까지 순회하면 n개의 숫자로 이루어진 이진수 집합을 모두 순회할 수 있고, A가 B의 부분집합일 때 항상 A가 먼저 등장한다.
A & B == A라면 A는 B의 부분집합이다.
A & (1 << n) 이면 A의 오른쪽에서 n-1번째 숫자가 무엇인지 알 수 있다(0번째 부터 시작)
n번째 숫자를 알 때, ^ 연산자를 통해 n번째 숫자를 반전시킬 수 있다.

댓글