Bitmask DP

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Held–Karp TSP DP: O(n^2 * 2^n) time, O(n * 2^n) space
5
// Input:
6
//   n (number of cities), followed by n x n cost matrix (long long)
7
//   Assumes a complete graph and cost[i][i] = 0. Returns to start city 0.
8
// Output:
9
//   Minimum tour cost and one optimal tour starting at 0.
10
11
int main() {
12
    ios::sync_with_stdio(false);
13
    cin.tie(nullptr);
14
15
    int n;
16
    if (!(cin >> n)) return 0;
17
    const long long INF = (1LL<<60);
18
    vector<vector<long long>> w(n, vector<long long>(n));
19
    for (int i = 0; i < n; ++i) {
20
        for (int j = 0; j < n; ++j) cin >> w[i][j];
21
    }
22
23
    int N = 1 << n; // total number of masks
24
    // dp[mask][j] = minimum cost to start at 0, visit exactly 'mask', and end at city j
25
    vector<vector<long long>> dp(N, vector<long long>(n, INF));
26
    vector<vector<int>> parent(N, vector<int>(n, -1)); // to reconstruct path
27
28
    // Base: only city 0 visited and we're at 0
29
    dp[1 << 0][0] = 0;
30
31
    // Iterate over all masks and last city j in mask
32
    for (int mask = 0; mask < N; ++mask) {
33
        if ((mask & 1) == 0) continue; // ensure tour starts at city 0 included
34
        for (int j = 0; j < n; ++j) {
35
            if (!(mask & (1 << j))) continue; // j must be in mask
36
            long long cur = dp[mask][j];
37
            if (cur == INF) continue;
38
            // Try to go to a next city k not in mask yet
39
            int rem = ((1 << n) - 1) ^ mask; // cities not yet visited
40
            for (int k = rem; k; k &= (k - 1)) {
41
                int bit = k & -k;           // least significant not-yet-visited bit
42
                int nxt = __builtin_ctz(bit); // index of that bit
43
                int nmask = mask | (1 << nxt);
44
                long long cand = cur + w[j][nxt];
45
                if (cand < dp[nmask][nxt]) {
46
                    dp[nmask][nxt] = cand;
47
                    parent[nmask][nxt] = j;
48
                }
49
            }
50
        }
51
    }
52
53
    // Close the cycle: return to 0 from some last city j
54
    long long ans = INF;
55
    int last = -1;
56
    int full = N - 1;
57
    for (int j = 1; j < n; ++j) {
58
        long long cand = dp[full][j] + w[j][0];
59
        if (cand < ans) {
60
            ans = cand;
61
            last = j;
62
        }
63
    }
64
65
    if (n == 1) {
66
        cout << 0 << "\n" << 0 << "\n"; // trivial case
67
        return 0;
68
    }
69
70
    cout << ans << "\n";
71
72
    // Reconstruct path backwards from (full, last)
73
    vector<int> tour;
74
    int mask = full;
75
    int j = last;
76
    while (j != -1) {
77
        tour.push_back(j);
78
        int pj = parent[mask][j];
79
        mask ^= (1 << j);
80
        j = pj;
81
    }
82
    tour.push_back(0); // add start to complete the cycle on output if desired
83
    reverse(tour.begin(), tour.end());
84
85
    // Print a Hamiltonian cycle starting and ending at 0
86
    // We'll print n+1 nodes to show the cycle explicitly
87
    for (int i = 0; i < n; ++i) cout << tour[i] << ' ';
88
    cout << 0 << '\n';
89
    return 0;
90
}
91

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// dp[mask] = minimal cost to assign the first popcount(mask) people to the set of tasks in 'mask'
5
// Transition: pick next person k = popcount(mask), assign them to any task j not in mask
6
// Input: n, then n x n cost matrix cost[k][j]
7
8
int main() {
9
    ios::sync_with_stdio(false);
10
    cin.tie(nullptr);
11
12
    int n; 
13
    if (!(cin >> n)) return 0;
14
    const long long INF = (1LL<<60);
15
    vector<vector<long long>> cost(n, vector<long long>(n));
16
    for (int i = 0; i < n; ++i)
17
        for (int j = 0; j < n; ++j)
18
            cin >> cost[i][j];
19
20
    int N = 1 << n;
21
    vector<long long> dp(N, INF);
22
    vector<int> parentTask(N, -1); // which task was assigned to reach this mask
23
    vector<int> parentMask(N, -1); // previous mask
24
    dp[0] = 0;
25
26
    for (int mask = 0; mask < N; ++mask) {
27
        long long cur = dp[mask];
28
        if (cur == INF) continue;
29
        int k = __builtin_popcount((unsigned)mask); // next person index
30
        if (k == n) continue; // all assigned
31
        int rem = ((1 << n) - 1) ^ mask; // tasks not yet taken
32
        for (int s = rem; s; s &= (s - 1)) {
33
            int bit = s & -s;
34
            int j = __builtin_ctz(bit);
35
            int nmask = mask | (1 << j);
36
            long long cand = cur + cost[k][j];
37
            if (cand < dp[nmask]) {
38
                dp[nmask] = cand;
39
                parentTask[nmask] = j;
40
                parentMask[nmask] = mask;
41
            }
42
        }
43
    }
44
45
    long long ans = dp[N - 1];
46
    cout << ans << '\n';
47
48
    // Reconstruct assignment: person i assigned to task assign[i]
49
    vector<int> assign(n, -1);
50
    int mask = N - 1;
51
    for (int i = n - 1; i >= 0; --i) {
52
        int j = parentTask[mask];
53
        assign[i] = j;
54
        mask = parentMask[mask];
55
    }
56
    for (int i = 0; i < n; ++i) cout << "person " << i << " -> task " << assign[i] << '\n';
57
    return 0;
58
}
59

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Computes F[mask] = sum_{S subseteq mask} f[S] for all masks in O(n * 2^n)
5
// Input:
6
//   n (bits), then array f of length 2^n (long long)
7
// Output:
8
//   F array of length 2^n
9
10
int main() {
11
    ios::sync_with_stdio(false);
12
    cin.tie(nullptr);
13
14
    int n; 
15
    if (!(cin >> n)) return 0;
16
    int N = 1 << n;
17
    vector<long long> f(N), F(N);
18
    for (int m = 0; m < N; ++m) cin >> f[m];
19
    F = f; // initialize
20
21
    // Standard SOS DP: for each bit i, add contributions from masks with i-th bit off
22
    for (int i = 0; i < n; ++i) {
23
        for (int mask = 0; mask < N; ++mask) {
24
            if (mask & (1 << i)) {
25
                F[mask] += F[mask ^ (1 << i)];
26
            }
27
        }
28
    }
29
30
    for (int m = 0; m < N; ++m) {
31
        cout << F[m] << (m + 1 == N ? '\n' : ' ');
32
    }
33
    return 0;
34
}
35

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Demonstrates submask iteration: for a fixed mask M, iterate all submasks S of M
5
// including S = 0. Also shows how many submasks there are (2^{popcount(M)}).
6
7
int main() {
8
    ios::sync_with_stdio(false);
9
    cin.tie(nullptr);
10
11
    int n; unsigned M;
12
    if (!(cin >> n >> M)) return 0; // read n (bits) and a mask M (as unsigned integer)
13
14
    vector<unsigned> subs;
15
    // Non-empty submasks
16
    for (unsigned S = M; S; S = (S - 1) & M) subs.push_back(S);
17
    subs.push_back(0); // include empty submask explicitly
18
19
    sort(subs.begin(), subs.end());
20
    subs.erase(unique(subs.begin(), subs.end()), subs.end());
21
22
    cout << "Submasks of M:" << '\n';
23
    for (unsigned S : subs) {
24
        cout << S << " (bits set: " << __builtin_popcount(S) << ")\n";
25
    }
26
    cout << "Total submasks: " << subs.size() << "\n";
27
    cout << "Expected: 2^{popcount(M)} = " << (1u << __builtin_popcount(M)) << "\n";
28
    return 0;
29
}
30