如何将状压DP之子集枚举转化为？
摘要：什么是子集枚举？ 就是在状态压缩后，枚举该状态的子状态。 做法 1. 一个 (4^n) 做法，直接枚举所有情况，并判断两个集合 (S) 和 (T) 中 (T in S)。 for (int s = 0; s &am
什么是子集枚举？
就是在状态压缩后，枚举该状态的子状态。
做法
1. 一个 \(4^n\) 做法，直接枚举所有情况，并判断两个集合 \(S\) 和 \(T\) 中 \(T \in S\)。
for (int s = 0; s < (1 << n); s++) {
for (int t = 0; t < (1 << n); t++) {
if ((s & t) == t) {
// t是s的子集
}
}
}
2. \(3^n\) 做法，借助位运算降低复杂度。
for (int s = 0; s < (1 << n); s++) {
for (int t = s; t; t = (t - 1)&s) {
// t是s的子集
}
}
复杂度证明
假设集合大小为 \(n\)。
对于一个特定的 \(mask\)，如果它包含 \(k\) 个 \(1\)，那么它有 \(2^k\) 个子集。
\(mask\) 中包含 \(k\) 个 \(1\) 的情况共有 \(C_n^k\)（即组合数 $ {n \choose k} $ ）种。
因此总的操作次数为：
\[\sum_{k=0}^n {n \choose k} 2 ^ k
\]
由二项式定理\((x + y) ^ n = \sum {n \choose k} x^k y^{n-k}\)可得：
代入 \(x = 2, y = 1\) 得 $$ \sum_{k=0}^n {n \choose k} 2^k 1^{n-k} = (2 + 1) ^ n = 3^n $$
简单例题：Cows in a Skyscraper G
做法
两种做法。
搜索
用 \(sum\) 数组存下每个电梯所装的奶牛的重量。
dfs 中传入两个参数：\((r, cnt)\)
分别表示：当前奶牛和电梯数量。
现在就简单了，在每一次 dfs 中，枚举每一个电梯。
如果能装进此电梯，就装进去，并往下。
枚举完了再 dfs 一次，表示增加一个电梯。
最后记录最小值即可。
有几个剪枝方案。
如果当前的电梯数量已经大于了最小的数量，那么就不枚举了。
在 dfs 前，将奶牛的重量从大到小的排序，这样就减少了可行方案。
戳我看代码喵~
int n, w;
lint val[N];
lint sum[N];
int ans = 1e9;
bool vis[N];
void dfs(int r, int cnt) {
if (cnt > ans) return ;
if (r == n) {
ans = min(ans, cnt);
return ;
}
for (int i = 0; i < cnt; i++) if (sum[i] + val[r] <= w) {
sum[i] += val[r];
dfs(r + 1, cnt);
sum[i] -= val[r];
}
sum[cnt] = val[r];
dfs(r + 1, cnt + 1);
sum[cnt] = 0;
}
int main() {
n = re, w = re;
for (int i = 0; i < n; i++) val[i] = re;
sort(val, val + n, greater<int>());
dfs(0, 1);
wr(ans), endl;
}
DP做法
这种做法还要分两种做法。
$O(3^n) $ 做法
\(dp_s\) 表示状态为 \(s\) 时，需要的最少电梯次数。
转移式还是很简单
\[dp_s = min(dp_{s \oplus t}),{t \subseteq s}
\]
戳我喵~
int n, w;
lint val[30], W[(1 << 18) + 10];
lint dp[(1 << 18) + 10];
signed main() {
IAKIOI;
n = re, w = re;
for (int i = 0; i < n; i++) val[i] = re;
memset(dp, 0x3f, sizeof dp);
dp[0]=0;
for (int s = 1; s < (1 << n); s++) for (int i = 0; i < n; i++) if ((s >> i) & 1) W[s] += val[i];
for (int s = 1; s < (1 << n); s++) for (int t = s; t; t = (t - 1) & s) if (W[t] <= w) dp[s] = min(dp[s], dp[s ^ t] + 1);
wr(dp[(1 << n) - 1]), endl;
}
\(O(2 ^ n \times n ^ 2)\) 做法
$ dp_{i, s} $：表示当前已经开启了 \(i\) 架电梯, 且当前已下楼奶牛的状态为 \(s\) 的情况下，最后一架电梯当前的载重量。
当前电梯还能装下，即不用新开电梯
那么
\[dp_{i, s | (1 << k)} = min(dp_{i, s} + val_k)
\]
当前电梯不能装下，即需要新开电梯
那么
\[dp_{i + 1, s | (1 << k)} = min(val_k)
\]
戳我喵~
int n, w;
int val[30];
int dp[30][(1 << 21) + 10];
signed main() {
IAKIOI;
n = re, w = re;
for (int i = 0; i < n; i++) val[i] = re;
memset(dp, INF, sizeof dp);
for (int i = 0; i < n; i++) dp[i + 1][1 << i] = val[i];
for (int s = 1; s < (1 << n); s++) for (int i = 1; i <= n; i++) if (dp[i][s] <= w) for (int k = 0; k < n; k++) if (!((s >> k) & 1)) {
if (dp[i][s] + val[k] <= w) dp[i][s | (1 << k)] = min(dp[i][s | (1 << k)], dp[i][s] + val[k]);
else dp[i + 1][s | (1 << k)] = min(dp[i + 1][s | (1 << k)], val[k]);
}
for (int i = 1; i <= n; i++) if (dp[i][(1 << n) - 1] != INF) {
wr(i), endl;
return 0;
}
}
3. $2 ^ n \times n$ 的做法（适用于$1 \le n \le 22$）
我们可以优化掉第二种做法的第一维。
\(dp_s\) 表示在 \(s\) 的状态下的最小电梯数。
我们再增加一个数组 \(sum_s\) 表示在 \(s\) 的状态下的最后一个电梯的最小载重。
剩下的和第二种做法基本相同。
戳我喵~
int dp[(1 << 22) + 10], sum[(1 << 22) + 10];
int val[23];
signed main() {
IAKIOI;
int n = re, w = re;
for (int i = 0; i < n; i++) val[i] = re;
memset(dp, 0x3f, sizeof dp);
memset(sum, 0x3f, sizeof sum);
for (int i = 0; i < n; i++) dp[1 << i] = 1, sum[1 << i] = val[i];
for (int s = 1; s < (1 << n); s++) for (int i = 0; i < n; i++) if (!((s >> i) & 1)) {
if (sum[s] + val[i] <= w) dp[s + (1 << i)] = min(dp[s + (1 << i)], dp[s]), sum[s + (1 << i)] = min(sum[s + (1 << i)], sum[s] + val[i]);
else dp[s + (1 << i)] = min(dp[s + (1 << i)], dp[s] + 1), sum[s + (1 << i)] = min(sum[s + (1 << i)], val[i]);
}
cout << dp[(1 << n) - 1] << '\n';
}