枚举¶
简介¶
枚举是一种通过暴力枚举状态来猜测可能得解的一种解题策略。通常来说，我们可以限定枚举的范围让它的复杂度更高。虽然这是一种非常基础的算法，但是后面的很多算法都是基于枚举来实现的。
例题¶
烤鱼
好渴鹅想要吃一条美味程度为 \(n\) 的鱼，现在好渴鹅一共有 \(10\) 中调料，每一种调料都可以放 \(1\sim 3\) 克，而一条烤鱼的美味程度的值就是所放调料的克数之和。你需要输出所有美味程度为 \(n\) 的放调料方案。
我们可以枚举每一种调料放多少克，最后如果加起来正好等于了 \(n\) 就输出。
代码
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
for (int k = 1; k <= 3; k++) {
for (int l = 1; l <= 3; l++) {
for (int p = 1; p <= 3; p++) {
for (int o = 1; o <= 3; o++) {
for (int u = 1; u <= 3; u++) {
for (int m = 1; m <= 3; m++) {
for (int y = 1; y <= 3; y++) {
for (int t = 1; t <= 3; t++) {
if (i + j + k + l + p + o + u + m + y + t == n) {
cout << i << ' ' << j << ' ' << k << ' ' << l << ' ' << p << ' ' << o << ' ' << u << ' ' << m << ' ' << y << ' ' << t << '\n';
}
}
}
}
}
}
}
}
}
}
}
这代码看起来长，但是它的思路其实非常简单——枚举所有的可能，然后注意判断就行了。但是我们发现，如果 \(i\) 早就大于等于了 \(n\)，那么继续枚举下去显然没有了意义，因此我们可以进行优化。其他的循环变量也是如此。
代码
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= min(3, n - i); j++) {
for (int k = 1; k <= min(3, n - i - j); k++) {
for (int l = 1; l <= min(3, n - i - j - k); l++) {
for (int p = 1; p <= min(3, n - i - j - k - l); p++) {
for (int o = 1; o <= min(3, n - i - j - k - l - p); o++) {
for (int u = 1; u <= min(3, n - i - j - k - l - p - o); u++) {
for (int m = 1; m <= min(3, n - i - j - k - l - p - o - u); m++) {
for (int y = 1; y <= min(3, n - i - j - k - l - p - o - u - m); y++) {
for (int t = 1; t <= min(3, n - i - j - k - l - p - o - u - m - y); t++) {
if (i + j + k + l + p + o + u + m + y + t == n) {
cout << i << ' ' << j << ' ' << k << ' ' << l << ' ' << p << ' ' << o << ' ' << u << ' ' << m << ' ' << y << ' ' << t << '\n';
}
}
}
}
}
}
}
}
}
}
}
但是，我们发现，如果可以有 \(m\) 中材料选择，那么这题用普通的枚举就很难办了，因此，可以去搜索板块学习“更优秀的枚举”。