很复杂的剪枝题 稍微不注意就会TLE
在本题中主要有两大类剪枝:
1. 优化搜索顺序
将木棍长度从大到小排序,优先尝试较长的木棍
2. 排除等效冗余
(1). 按照组合数的方式枚举小棍
(2). 对于当前的大棒,记录最近一次的小棍的长度,如果该分支失败,则跳过所有与该小棍长度相同的小棍
(3). 如果当前的小棍是第一根,并且该分支搜索失败了,那么直接回溯
(4). 如果当前的小棍是最后一根,并且该分支搜索失败,那么直接回溯
代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 20;
int a[maxn], sum[maxn];
int res = maxn;
int n, w;
void dfs(int u, int cnt)
{
if(cnt >= res) return;
if(u == n){
res = cnt;
return;
}
for(int i = 0; i < cnt; i ++){
if(sum[i] + a[u] <= w){
sum[i] += a[u];
dfs(u + 1, cnt);
sum[i] -= a[u];
}
}
sum[cnt] = a[u];
dfs(u + 1, cnt + 1);
sum[cnt] = 0;
}
int main()
{
cin >> n >> w;
for(int i = 0; i < n; i ++) cin >> a[i];
sort(a, a + n);
reverse(a, a + n);
dfs(0, 0);
cout << res << endl;
return 0;
}