Bitmask DP - Subset Enumeration

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Helper to print a mask as a bitstring of length n
5
string bits(unsigned m, int n){
6
    string s(n, '0');
7
    for(int i = 0; i < n; ++i) if(m & (1u<<i)) s[n-1-i] = '1'; // MSB on left for readability
8
    return s;
9
}
10
11
int main(){
12
    ios::sync_with_stdio(false);
13
    cin.tie(nullptr);
14
15
    int n = 5;                 // number of bits (universe size)
16
    unsigned mask = 0b10110u;  // the set {1,2,4}
17
18
    cout << "Mask(" << bits(mask, n) << ") submasks including empty:\n";
19
20
    // do-while form includes s == 0 exactly once
21
    unsigned s = mask;
22
    do {
23
        cout << bits(s, n) << "\n";
24
        if(s == 0) break;          // stop after processing empty submask
25
        s = (s - 1) & mask;        // next submask idiom
26
    } while(true);
27
28
    // Note: If you want to skip the empty submask, use for(s = mask; s > 0; s = (s-1) & mask)
29
30
    return 0;
31
}
32

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int main(){
5
    ios::sync_with_stdio(false);
6
    cin.tie(nullptr);
7
8
    int n = 18; // Keep n moderate; O(3^n) work. Try n <= 20 on typical judges.
9
    const int N = 1 << 18; // We will only use (1<<n) entries.
10
11
    // Read or generate input array A of size 2^n. Here we generate small random values.
12
    int size = 1 << n;
13
    vector<long long> A(size), F(size, 0);
14
    mt19937_64 rng(12345);
15
    uniform_int_distribution<int> dist(0, 9);
16
    for(int m = 0; m < size; ++m) A[m] = dist(rng);
17
18
    // Direct subset enumeration: F[m] = sum_{s subset m} A[s]
19
    for(int m = 0; m < size; ++m){
20
        long long acc = 0;
21
        unsigned s = (unsigned)m;
22
        // Enumerate all submasks including 0 via do-while
23
        do {
24
            acc += A[s];
25
            if(s == 0) break;
26
            s = (s - 1u) & (unsigned)m;
27
        } while(true);
28
        F[m] = acc;
29
    }
30
31
    // Output a small sample
32
    for(int m = 0; m < min(size, 8); ++m){
33
        cout << "m=" << m << " F[m]=" << F[m] << '\n';
34
    }
35
36
    // Note: For large n, prefer SOS DP (O(n 2^n)) to compute all F faster.
37
    return 0;
38
}
39

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int main(){
5
    ios::sync_with_stdio(false);
6
    cin.tie(nullptr);
7
8
    int n = 6;                             // number of features
9
    int size = 1 << n;
10
11
    // Suppose cost[s] is known for each set s (e.g., price of a bundle). We'll generate mock costs.
12
    vector<int> cost(size, INT_MAX/4);
13
    // Some random bundles with random costs
14
    vector<pair<unsigned,int>> bundles = {
15
        {0b000111u, 5}, {0b101010u, 7}, {0b111000u, 4}, {0b111111u, 12}, {0b010001u, 3}
16
    };
17
    for(auto [b, c] : bundles) cost[b] = min(cost[b], c);
18
19
    // We want the minimal cost superset of required mask 'need' (e.g., required features)
20
    unsigned need = 0b001011u; // require features {0,1,3}
21
22
    // Precompute bestCost[s]: best available cost for exactly s (or INF if not sold)
23
    // If combining bundles is allowed, you would do DP over OR; here we pick exactly one superset
24
25
    int best = INT_MAX/4; unsigned arg = need;
26
    for(unsigned s = need; s < (1u<<n); s = (s + 1u) | need){
27
        if(cost[s] < best){ best = cost[s]; arg = s; }
28
    }
29
30
    if(best >= INT_MAX/4) cout << "No available superset found.\n";
31
    else {
32
        cout << "Best superset mask = " << bitset<6>(arg) << ", cost = " << best << "\n";
33
    }
34
35
    return 0;
36
}
37

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// We are given n elements (n <= 20) and a boolean array allowed[s] for all submasks s.
5
// In one step, we may take any allowed non-empty submask of the remaining elements.
6
// Goal: cover all elements with the minimum number of steps.
7
8
int main(){
9
    ios::sync_with_stdio(false);
10
    cin.tie(nullptr);
11
12
    int n = 12;                    // keep n moderate; DP is O(3^n) in worst case
13
    int N = 1 << n;
14
15
    // Example: an element set partitioned into 3 cliques of size 4; only subsets within a clique are allowed.
16
    // Build allowed[s] true iff s is subset of exactly one block of 4 consecutive indices.
17
    vector<char> allowed(N, 0);
18
    vector<int> blockStart = {0, 4, 8};
19
    for(int b : blockStart){
20
        int blockMask = 0;
21
        for(int i = 0; i < 4; ++i) blockMask |= (1 << (b + i));
22
        // all non-empty submasks of this block are allowed
23
        for(int s = blockMask; s; s = (s - 1) & blockMask) allowed[s] = 1;
24
    }
25
26
    const int INF = 1e9;
27
    vector<int> dp(N, INF);
28
    dp[0] = 0; // zero elements need zero groups
29
30
    // Iterate masks in increasing order of bits set for better cache behavior (optional)
31
    vector<int> order(N);
32
    iota(order.begin(), order.end(), 0);
33
    stable_sort(order.begin(), order.end(), [](int a, int b){ return __builtin_popcount((unsigned)a) < __builtin_popcount((unsigned)b); });
34
35
    for(int m : order){
36
        if(dp[m] == INF) continue;
37
        if(m == N-1) continue; // already full
38
        // remaining elements to cover
39
        unsigned rem = ((unsigned)N - 1u) ^ (unsigned)m;
40
        if(rem == 0) continue;
41
        // Choose a pivot (least significant remaining bit) to avoid duplicates in grouping order
42
        unsigned pivot = rem & -rem; // lowbit
43
        // Enumerate submasks s of rem that include pivot and are allowed
44
        for(unsigned s = rem; s; s = (s - 1u) & rem){
45
            if(!(s & pivot)) continue;      // enforce pivot in s to avoid permutations
46
            if(!allowed[s]) continue;       // only allowed groups
47
            int nm = m | (int)s;
48
            dp[nm] = min(dp[nm], dp[m] + 1);
49
        }
50
    }
51
52
    int ans = dp[N-1];
53
    cout << "Minimum number of groups to cover all elements: " << ans << "\n";
54
55
    return 0;
56
}
57