set_cover.cpp

// set_cover.cpp
// -----------------------------------------------------------------
// Set Cover（集合覆蓋）：
//   1. 貪婪近似：每輪挑「新覆蓋元素最多」的集合，保證 <= (ln n + 1)·OPT
//   2. 精確解：位元枚舉（子集合數量小時）
//   3. 貪婪比最優差的經典構造範例
//
// Compile: g++ -std=c++17 -O2 -Wall -Wextra -o set_cover set_cover.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

// 全集 = {0, 1, ..., n-1}，每個集合用 bitmask（n <= 30）
// ---------- 1. 貪婪近似 ----------
vector<int> setCoverGreedy(int n, const vector<unsigned>& sets, bool verbose = false) {
    unsigned universe = (n == 32) ? ~0u : ((1u << n) - 1);
    unsigned covered = 0;
    vector<int> picked;
    int round = 0;
    while (covered != universe) {
        int best = -1, bestGain = 0;
        for (int i = 0; i < (int)sets.size(); ++i) {
            int gain = __builtin_popcount(sets[i] & ~covered);
            if (gain > bestGain) { bestGain = gain; best = i; }
        }
        if (best == -1) break;                          // 蓋不完（輸入有問題）
        covered |= sets[best];
        picked.push_back(best);
        if (verbose)
            cout << "  round " << ++round << ": pick S" << best
                 << " (+" << bestGain << " new, covered "
                 << __builtin_popcount(covered) << "/" << n << ")\n";
    }
    return picked;
}

// ---------- 2. 精確解：枚舉所有集合組合 O(2^m) ----------
vector<int> setCoverExact(int n, const vector<unsigned>& sets) {
    int m = (int)sets.size();
    unsigned universe = (n == 32) ? ~0u : ((1u << n) - 1);
    int best = m + 1;
    unsigned bestMask = 0;
    for (unsigned mask = 0; mask < (1u << m); ++mask) {
        if (__builtin_popcount(mask) >= best) continue;
        unsigned covered = 0;
        for (int i = 0; i < m; ++i)
            if ((mask >> i) & 1) covered |= sets[i];
        if (covered == universe) {
            best = __builtin_popcount(mask);
            bestMask = mask;
        }
    }
    vector<int> out;
    for (int i = 0; i < m; ++i)
        if ((bestMask >> i) & 1) out.push_back(i);
    return out;
}

static unsigned makeSet(const vector<int>& elems) {
    unsigned s = 0;
    for (int e : elems) s |= 1u << e;
    return s;
}

static void printPick(const string& tag, const vector<int>& p) {
    cout << tag << " uses " << p.size() << " sets: {";
    for (size_t i = 0; i < p.size(); ++i)
        cout << "S" << p[i] << (i + 1 < p.size() ? "," : "");
    cout << "}\n";
}

int main() {
    // ---- 範例 1：教科書例（貪婪=最優） ----
    cout << "=== Example 1: textbook instance ===\n";
    // 全集 {0..11}，6 個集合
    vector<unsigned> sets1 = {
        makeSet({0,1,2,3}),          // S0
        makeSet({4,5,6,7}),          // S1
        makeSet({8,9,10,11}),        // S2
        makeSet({0,4,8}),            // S3
        makeSet({1,5,9}),            // S4
        makeSet({2,3,6,7,10,11})     // S5
    };
    cout << "universe = {0..11}\n";
    auto g1 = setCoverGreedy(12, sets1, true);
    printPick("greedy", g1);
    printPick("exact ", setCoverExact(12, sets1));
    cout << "\n";

    // ---- 範例 2：讓貪婪失手的構造 ----
    cout << "=== Example 2: instance where greedy loses ===\n";
    // 全集 {0..13}。OPT = 2（S0, S1 各蓋一半）
    // 但貪婪先咬走大集合 S2 (8 個)，之後還要 2 個 -> 用 3 個
    vector<unsigned> sets2 = {
        makeSet({0,1,2,3,4,5,6}),        // S0: 上半
        makeSet({7,8,9,10,11,12,13}),    // S1: 下半
        makeSet({0,1,2,3,7,8,9,10}),     // S2: 誘餌（8 個元素，最大）
    };
    auto g2 = setCoverGreedy(14, sets2, true);
    printPick("greedy", g2);
    printPick("exact ", setCoverExact(14, sets2));
    cout << "greedy/OPT = " << (double)g2.size() / 2 << "  (bound: ln(14)+1 = "
         << log(14.0) + 1 << ")\n\n";

    // ---- 範例 3：消防站選址情境 ----
    cout << "=== Example 3: fire station placement ===\n";
    // 10 個街區，5 個候選站址，各站可涵蓋的街區：
    vector<unsigned> stations = {
        makeSet({0,1,2}),        // 站 0
        makeSet({2,3,4,5}),      // 站 1
        makeSet({5,6,7}),        // 站 2
        makeSet({7,8,9}),        // 站 3
        makeSet({1,3,6,8})       // 站 4
    };
    cout << "10 blocks, 5 candidate stations\n";
    auto g3 = setCoverGreedy(10, stations, true);
    printPick("greedy", g3);
    printPick("exact ", setCoverExact(10, stations));
    cout << "\n";

    // ---- 範例 4：理論界的驗證——隨機大量實例 ----
    cout << "=== Example 4: greedy vs OPT over random instances ===\n";
    unsigned seed = 555;
    auto nextRand = [&seed]() {
        seed = seed * 1103515245 + 12345;
        return (seed >> 16) & 0x7fff;
    };
    int n = 16, m = 12, trials = 200;
    double worstRatio = 1.0;
    int greedyWins = 0, ties = 0;
    for (int t = 0; t < trials; ++t) {
        vector<unsigned> ss;
        unsigned covered = 0;
        for (int i = 0; i < m; ++i) {
            unsigned s = 0;
            for (int e = 0; e < n; ++e)
                if (nextRand() % 100 < 30) s |= 1u << e;
            ss.push_back(s);
            covered |= s;
        }
        if (covered != (1u << n) - 1) { --t; continue; }  // 重抽：必須可覆蓋
        auto g = setCoverGreedy(n, ss);
        auto e = setCoverExact(n, ss);
        double r = (double)g.size() / e.size();
        worstRatio = max(worstRatio, r);
        if (g.size() == e.size()) ++ties;
        else ++greedyWins;                                // 其實是 greedy 較差
    }
    cout << trials << " random instances (n=16, m=12, p=0.3):\n";
    cout << "greedy == OPT: " << ties << " times, greedy > OPT: "
         << greedyWins << " times\n";
    cout << "worst greedy/OPT ratio observed = " << worstRatio
         << "  (theory bound: ln(16)+1 = " << log(16.0) + 1 << ")\n";
    return 0;
}