# 剪枝

## 1.优化剪枝顺序

1. 在“小猫爬山”问题中，把小猫按照重量递减的顺序进行搜索
2. 在“数独”问题中，优先搜索“能填的合法数字”最少位置

# AcWing 165. 小猫爬山

``````5 1996
1
2
1994
12
29
``````

``2``

``````#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;

int n, m;
int w[N];
int sum[N];
int ans = N;

void dfs(int u, int k)
{
// 最优性剪枝
if(k >= ans) return;
if(u == n)
{
ans = k;
return ;
}

for(int i = 0; i < k; i ++ )
if(sum[i] + w[u] <= m)
{
sum[i] += w[u];
dfs(u + 1, k);
sum[i] -= w[u];
}

sum[k] = w[u];
dfs(u + 1, k + 1);
sum[k] = 0;
}

int main()
{
cin >> n >> m;
for(int i = 0; i < n; i ++ ) cin >> w[i];

// 优化搜索顺序
sort(w, w + n);
reverse(w, w + n);

dfs(0, 0);

cout << ans << endl;

return 0;
}``````

# AcWing 166. 数独

``````4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end
``````

``````417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936``````

``````#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 9, M = 1 << N;

int ones[M], map[M];
int row[N], col[N], cell[3][3];
char str[100];

void init()
{
for (int i = 0; i < N; i ++ )
row[i] = col[i] = (1 << N) - 1;

for (int i = 0; i < 3; i ++ )
for (int j = 0; j < 3; j ++ )
cell[i][j] = (1 << N) - 1;
}

void draw(int x, int y, int t, bool is_set)
{
if (is_set) str[x * N + y] = '1' + t;
else str[x * N + y] = '.';

int v = 1 << t;
if (!is_set) v = -v;

row[x] -= v;
col[y] -= v;
cell[x / 3][y / 3] -= v;
}

int lowbit(int x)
{
return x & -x;
}

int get(int x, int y)
{
return row[x] & col[y] & cell[x / 3][y / 3];
}

bool dfs(int cnt)
{
if (!cnt) return true;

int minv = 10;
int x, y;
for (int i = 0; i < N; i ++ )
for (int j = 0; j < N; j ++ )
if (str[i * N + j] == '.')
{
int state = get(i, j);
if (ones[state] < minv)
{
minv = ones[state];
x = i, y = j;
}
}

int state = get(x, y);
for (int i = state; i; i -= lowbit(i))
{
int t = map[lowbit(i)];
draw(x, y, t, true);
if (dfs(cnt - 1)) return true;
draw(x, y, t, false);
}

return false;
}

int main()
{
for (int i = 0; i < N; i ++ ) map[1 << i] = i;
for (int i = 0; i < 1 << N; i ++ )
for (int j = 0; j < N; j ++ )
ones[i] += i >> j & 1;

while (cin >> str, str[0] != 'e')
{
init();

int cnt = 0;
for (int i = 0, k = 0; i < N; i ++ )
for (int j = 0; j < N; j ++, k ++ )
if (str[k] != '.')
{
int t = str[k] - '1';
draw(i, j, t, true);
}
else cnt ++ ;

dfs(cnt);

puts(str);
}

return 0;
}
``````

# AcWing 167. 木棒

``````9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
``````

``````6
5``````

# AcWing 168. 生日蛋糕

``````100
2
``````

``68``

THE END

)">