如何将状压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\) 时，需要的最少电梯次数。