Untuk persoalan dengan himpunan kecil (≤ 20-25 elemen), kita bisa merepresentasikan setiap himpunan sebagai integer bitmask. Bit ke-i = 1 berarti elemen ke-i ada di himpunan. Operasi himpunan (union, intersection, complement, subset check) menjadi operasi bitwise O(1). Hal ini memungkinkan DP bitmask untuk persoalan NP-hard kecil (TSP, exact cover, vertex cover exact) dan SOS DP (Sum Over Subsets) untuk prekalkulasi aggregate atas subset. Pada Chapter ini kita membedah enumerasi subset, popcount, dan SOS DP — teknik fundamental yang sering muncul di kompetisi dan interview.

Aturan: Himpunan sebagai Bitmask #

Misal himpunan S = {0, 1, 2, ..., n-1}. Setiap subset direpresentasikan sebagai integer di [0, 2^n - 1] di mana bit ke-i = 1 iff elemen i ada di subset.

Operasi standar:

OperasiBitwiseKeterangan
A ∪ B (union)a | bOR
A ∩ B (intersection)a & bAND
A \ B (difference)a & ~bAND NOT
A ⊆ B (subset)(a & b) == acheck subset
`A` (size)
~A (complement)~a & ((1<<n) - 1)mask universe
Lowest set bita & (-a)isolasi LSB
Hapus LSBa & (a - 1)clear LSB

Mekanisme: Enumerasi Subset dan SOS DP #

Enumerasi Semua Subset dari Mask #

Untuk mask M, iterasi semua sub ⊆ M dengan trik:

cpp 
int sub = M;
do {
    // process sub
    sub = (sub - 1) & M;
} while (sub != M);

sub = (sub - 1) & M mengurangi sub sebesar 1 lalu menjaganya tetap submask dari M. Loop berakhir saat sub kembali ke M (sudah cycle). Bila ingin exclude empty set: mulai sub = M dan berhenti saat sub == 0.

Total subset dari mask dengan k bit set = 2^k. Iterasi O(2^k).

SOS DP (Sum Over Subsets) #

Diberikan fungsi f[mask] untuk setiap mask. Hitung F[mask] = Σ f[sub] untuk semua sub ⊆ mask.

Naif: untuk setiap mask, iterasi semua subset. O(3^n) total.

SOS DP: gunakan DP dengan iterasi bit per bit.

text 
for (int i = 0; i < K; ++i) {
    for (int mask = 0; mask < (1 << K); ++mask) {
        if (mask & (1 << i)) {
            F[mask] += F[mask ^ (1 << i)];
        }
    }
}

Intuisi: setelah iterasi bit ke-i selesai, F[mask] = sum dari f[sub] untuk semua sub ⊆ mask yang berbeda dari mask hanya pada bit-bit 0..i. Setelah K iterasi, F[mask] = sum untuk semua sub ⊆ mask. Kompleksitas O(K · 2^K) = O(n log n) di mana n = 2^K.

Implementasi: Enumerasi, Popcount, SOS DP #

cpp 
#include <iostream>
#include <vector>
#include <algorithm>

// SOS DP (Sum Over Subsets)
// For each mask, compute sum of f[sub] for all sub that is submask of mask
std::vector<long long> sos_dp(const std::vector<long long>& f) {
    int n = f.size();
    int K = 0;
    while ((1 << K) < n) K++;
    std::vector<long long> F = f;
    for (int i = 0; i < K; ++i) {
        for (int mask = 0; mask < n; ++mask) {
            if (mask & (1 << i)) {
                F[mask] += F[mask ^ (1 << i)];
            }
        }
    }
    return F;
}

// Subset enumeration: iterasi semua submask dari mask
void enumerate_subsets(int mask) {
    std::cout << "Subsets of mask " << mask << " (binary ";
    for (int i = 3; i >= 0; --i) std::cout << ((mask >> i) & 1);
    std::cout << "):\n  ";
    int sub = mask;
    do {
        std::cout << "(";
        for (int i = 3; i >= 0; --i) std::cout << ((sub >> i) & 1);
        std::cout << ") ";
        sub = (sub - 1) & mask;
    } while (sub != mask);
    std::cout << '\n';
}

int popcount(int x) { return __builtin_popcount(x); }

int main() {
    std::cout << "Popcount demo:\n";
    int vals[] = {0, 1, 3, 7, 15, 255, 1023};
    for (int v : vals) {
        std::cout << "  popcount(" << v << ") = " << popcount(v) << '\n';
    }

    std::cout << "\nSubset enumeration:\n";
    enumerate_subsets(0b1011);
    enumerate_subsets(0b1110);

    std::cout << "\nSOS DP demo:\n";
    std::vector<long long> f(8);
    for (int i = 0; i < 8; ++i) f[i] = i;  // f[mask] = mask
    auto F = sos_dp(f);
    for (int i = 0; i < 8; ++i) {
        std::cout << "  F[" << i << "] = " << F[i] << '\n';
    }

    std::cout << "\nVerifikasi manual untuk F[7] (mask=111):\n";
    std::cout << "  Subsets of 7: 0, 1, 2, 3, 4, 5, 6, 7\n";
    std::cout << "  Sum = 0+1+2+3+4+5+6+7 = 28\n";
    return 0;
}

Output yang Dihasilkan:

text 
Popcount demo:
  popcount(0) = 0
  popcount(1) = 1
  popcount(3) = 2
  popcount(7) = 3
  popcount(15) = 4
  popcount(255) = 8
  popcount(1023) = 10

Subset enumeration:
Subsets of mask 11 (binary 1011):
  (1011) (1010) (1001) (1000) (0011) (0010) (0001) (0000) 
Subsets of mask 14 (binary 1110):
  (1110) (1100) (1010) (1000) (0110) (0100) (0010) (0000) 

SOS DP demo:
  F[0] = 0
  F[1] = 1
  F[2] = 2
  F[3] = 6
  F[4] = 4
  F[5] = 10
  F[6] = 12
  F[7] = 28

Verifikasi manual untuk F[7] (mask=111):
  Subsets of 7: 0, 1, 2, 3, 4, 5, 6, 7
  Sum = 0+1+2+3+4+5+6+7 = 28

Bedah Kode Baris-per-Baris #

  1. __builtin_popcount(x): GCC builtin untuk menghitung jumlah bit 1. Sama dengan std::popcount C++20. Lebih cepat dari loop manual.
  2. enumerate_subsets: iterasi semua submask dari mask dengan trik sub = (sub - 1) & mask. Awal sub = mask, akhir sub = mask lagi (sudah cycle). Total 2^k iterasi di mana k = jumlah bit 1 di mask.
  3. sub = (sub - 1) & mask: trik enumerasi subset. sub - 1 mengurangi 1, lalu & mask memastikan hanya bit-bit yang ada di mask yang tetap set. Hasilnya submask berikutnya dalam urutan descending.
  4. sos_dp: inisialisasi F = f. Iterasi K kali (K = bit width). Setiap iterasi, untuk setiap mask dengan bit i set, F[mask] += F[mask ^ (1<<i)]. Ini menambah kontribusi submask yang berbeda hanya pada bit i.
  5. if (mask & (1 << i)): hanya proses mask yang punya bit i set. mask ^ (1 << i) = mask dengan bit i di-toggle (di sini berarti di-clear karena bit i pasti set).
  6. F[mask] += F[mask ^ (1 << i)]: tambah kontribusi submask tanpa bit i. Setelah K iterasi, F[mask] = sum dari semua f[sub] untuk sub ⊆ mask.
  7. Verifikasi SOS:
    • f[mask] = mask (identity).
    • F[7] (mask=111, semua bit set) = sum dari f untuk semua subset = 0+1+2+3+4+5+6+7 = 28. ✓
    • F[3] (mask=011) = sum dari f untuk subset {0,1,2,3} = 0+1+2+3 = 6. ✓
    • F[5] (mask=101) = sum dari f untuk subset {0,1,4,5} = 0+1+4+5 = 10. ✓

Aplikasi DP Bitmask #

TSP (Traveling Salesman Problem) #

Diberikan graph lengkap dengan n node, cari tour minimum yang mengunjungi semua node. DP state: dp[mask][last] = minimum cost untuk mengunjungi semua node di mask, berakhir di node last.

cpp 
// dp[mask][last] = min cost to visit nodes in mask, ending at last
dp[1][0] = 0;  // start at node 0
for (int mask = 1; mask < (1 << n); ++mask) {
    for (int last = 0; last < n; ++last) {
        if (!(mask & (1 << last))) continue;
        for (int next = 0; next < n; ++next) {
            if (mask & (1 << next)) continue;
            int new_mask = mask | (1 << next);
            dp[new_mask][next] = std::min(dp[new_mask][next],
                                          dp[mask][last] + dist[last][next]);
        }
    }
}
// answer = min(dp[(1<<n)-1][last] + dist[last][0]) for all last

Kompleksitas O(n² · 2^n). Untuk n ≤ 20, ini feasible.

Vertex Cover Exact #

DP bitmask untuk minimum vertex cover: coba semua subset vertex, periksa apakah vertex cover valid (setiap edge punya endpoint di subset). O(2^n · m). Untuk n ≤ 25, feasible.

Maximum Independent Set (MIS) #

Untuk graph dengan n ≤ 40-50, meet in the middle: pecah node jadi dua bagian A dan B. Precompute MIS untuk semua subset A dan subset B. Untuk kombinasi, cek compatibility (no edge antara A dan B subset yang dipilih).

SOS DP Aplikasi #

  1. Count subset with property: count berapa subset sub ⊆ mask yang memenuhi kondisi tertentu.
  2. Subset convolution: f * g (mask) = Σ f[sub] * g[mask \ sub]. Penting untuk Steiner tree problem, vertex cover counting.
  3. Connected subgraph count: hitung berapa subgraph terhubung untuk setiap subset node.

Kompleksitas #

TeknikKompleksitasn Max Praktis
Subset enumeration per maskO(2^k) di mana k = popcountk ≤ 25
Total enumerasi semua subsetO(3^n)n ≤ 18
SOS DPO(n · 2^n)n ≤ 20
DP bitmask TSPO(n² · 2^n)n ≤ 20
Exact vertex coverO(2^n · m)n ≤ 25

Ringkasan #

  • Bitmask = representasi himpunan kecil sebagai integer. Operasi himpunan jadi bitwise O(1).
  • Enumerasi subset: sub = (sub - 1) & mask. Total 2^k iterasi untuk mask dengan k bit set.
  • Popcount: __builtin_popcount(x) untuk count bit 1.
  • SOS DP: precompute F[mask] = Σ f[sub] untuk sub ⊆ mask. Kompleksitas O(n · 2^n).
  • DP bitmask TSP: dp[mask][last] = min cost visit mask, end at last. O(n² · 2^n).
  • Batas praktis: n ≤ 20 untuk DP bitmask, n ≤ 25 untuk exact vertex cover, n ≤ 18 untuk enumerasi semua subset semua mask.