---
###### tags: `2021 師大附中資訊科暑期培訓`
---
# 枚舉
2021 師大附中資訊科暑期培訓
joylintp
---
## 密密麻麻密碼鎖
### NPSC 2017 國中決賽
----
有一個六位數的密碼鎖
現在上面顯示的數字為 $\overline{abcdef}$
每次操作你可以把其中一位數加上1或減去1
（9加上1變成0；0減去1變成9）
求至少要 $k$ 次操作才能使六位數字皆相異
並列出所有 $k$ 次操作後六位數字皆相異的可能狀態
----
~~遞迴~~
~~動態規劃~~
### 窮舉
----
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int mn = 2147483647;
set<int> anslist;
for (int i = 12345; i < 1000000; i++)
{
int t = i, u;
set<int> s;
if (i < 100000)
s.insert(0);
while (t)
s.insert(t % 10), t /= 10;
int tmp = 0;
if (s.size() == 6)
{
t = i;
u = n;
while (t || u)
tmp += min(abs(t % 10 - u % 10), 10 - abs(t % 10 - u % 10)), t /= 10, u /= 10;
if (tmp < mn)
anslist.clear(), anslist.insert(i), mn = tmp;
else if (tmp == mn)
anslist.insert(i);
else;
}
}
cout << anslist.size() << ' ' << mn << '\n';
for (int i : anslist)
cout << setw(6) << setfill('0') << i << ' ';
return 0;
}
```
---
## 數獨
----
* 遇到一個空格就枚舉所有可能
* 若沒有合法的數字就回到上一個空格
----
```cpp=
#include<bits/stdc++.h>
using namespace std;
bool chkR[9][10], chkC[9][10], chkB[9][10];
vector<int> g(81);
void dfs(int i)
{
if (i == 81)
{
for (int j = 0; j < 81; j++)
cout << g[j];
cout << '\n', exit(0);
}
else if (g[i] != 0)
dfs(i + 1);
else
{
for (int j = 1; j <= 9; j++)
{
int R = i / 9, C = i % 9, B = R / 3 * 3 + C / 3;
if (!chkR[R][j] && !chkC[C][j] && !chkB[B][j])
{
g[i] = j, chkR[R][j] = chkC[C][j] = chkB[B][j] = true;
dfs(i + 1);
g[i] = 0, chkR[R][j] = chkC[C][j] = chkB[B][j] = false;
}
}
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
string s;
cin >> s;
for (int i = 0; i < 81; i++)
{
if (s[i] == '.')
g[i] = 0;
else
{
g[i] = s[i] - '0';
int R = i / 9, C = i % 9, B = R / 3 * 3 + C / 3;
if (chkR[R][g[i]] || chkC[C][g[i]] || chkB[B][g[i]])
cout << "No solution.\n", exit(0);
chkR[R][g[i]] = chkC[C][g[i]] = chkB[B][g[i]] = true;
}
}
dfs(0);
cout << "No solution.\n";
return 0;
}
```
---
## 八皇后問題
----
* 對每一列枚舉放皇后的位置
* 若所有位置皆不合法則回到上一列
----
```cpp=
#include<bits/stdc++.h>
using namespace std;
bool chkC[11], chkD[21], chkE[21];
int N, g[11], ans;
void dfs(int R)
{
if (R == N)
{
for (int i = 0; i < N; i++, cout << '\n')
for (int j = 0; j < N; j++)
if (g[i] == j)
cout << 'Q';
else
cout << 'x';
cout << '\n', ans++;
}
else
{
for (int C = 0; C < N; C++)
{
int D = R + C, E = R - C + (N - 1);
if (!chkC[C] && !chkD[D] && !chkE[E])
{
g[R] = C, chkC[C] = chkD[D] = chkE[E] = true;
dfs(R + 1);
g[R] = -1, chkC[C] = chkD[D] = chkE[E] = false;
}
}
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N;
dfs(0);
cout << ans << "\n\n";
return 0;
}
```
---
## 背包問題
----
有 $n\ (1 \leq n \leq 20)$ 樣物品，
每個物品有自己的價值和重量 $(1 \leq p_i, w_i \leq 10^9)$
現在有一個耐重 $k\ (1 \leq k \leq 10^9)$ 的背包，
問在所有物品只能選擇全放進背包或全不放進背包的情況下，
背包內的物品總價值最高是多少？
----
* 枚舉物品的子集合
* 檢查子集合總重是否超過 $k$ 並更新最高價格
----
```cpp=
#include<bits/stdc++.h>
using namespace std;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k, p[20], w[20];
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> p[i] >> w[i];
int ttl = (1 << n);
long long ans = 0;
for (int i = 0; i < ttl; i++)
{
int t = i;
long long sumP = 0, sumW = 0
for (int j = 0; j < n; j++, t /= 2)
if (t % 2)
sumP += p[j], sumW += w[j];
if (sumW <= k)
ans = max(ans, sumP);
}
return 0;
}
```
---
## Next Permutation
----
```cpp=
bool my_next_permutation(vector<int> &num)
{
int n = num.size();
if(n == 1)
return false;
for(int i = n - 2, j = n - 1; i >= 0; i--, j--)
if(num[i] < num[j])
{
int k = n - 1;
while(num[i] >= num[k])
k--;
swap(num[i], num[k]);
reverse(num.begin() + j, num.end());
return true;
}
return false;
}
```
----
```cpp=
next_permutation(v.begin(), v.end()); // 將v變成下一個排列
```
```cpp=
prev_permutation(v.begin(), v.end()); // 將v變成前一個排列
```
---
## Lotto
### UVa 441, ZJ c074
----
* 枚舉大小為6的子集合
* 將use陣列內最後6個值設為1
* 以next_permutation遍歷所有大小為6的子集合
----
```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
bool fir = true;
int n;
while (cin >> n)
{
if (!n)
return 0;
if (fir)
fir = false;
else
cout << '\n';
vector<int> v(n);
for (int i = 0; i < n; i++)
cin >> v[i];
vector<bool> use(n);
for (int i = 0; i < 6; i++)
use[i] = true;
do
{
int cnt = 0;
for (int i = 0; i < n; i++)
if (use[i])
cout << v[i] << " \n"[cnt++ == 5];
} while (prev_permutation(use.begin(), use.end()));
}
return 0;
}
```
{"metaMigratedAt":"2023-06-15T11:45:34.744Z","metaMigratedFrom":"Content","title":"枚舉","breaks":true,"contributors":"[{\"id\":\"6b95215f-91a7-4eaf-bcfe-d43740108f96\",\"add\":10584,\"del\":4762}]"}