题目链接 $\mathfrak{165}$。
考察最优性剪枝。
题目描述
$n$ 只猫,用容量为 $w$ 的缆车装,求需要的最少缆车数。
样例
18 100000000
18381246
29249683
12495474
24844134
96242521
67846996
945213
27675252
58653213
12062801
4830609
83790642
10682393
27267295
60527976
8881456
3916444
32450339
解题思路
无优化
考虑每一只猫,我们只有两种选择:新开一辆缆车装它,或者把它塞进已有的任何一辆可以塞下它的缆车。暴搜即可,每次搜完更新答案。
优化 1
把所有猫按重量排序,这样会尽可能地把当前的猫塞进剩余容量较小的缆车,减少空间的浪费,从而尽早地更新答案,减小搜索树的大小。
别急着交 没有优化 2 优化 1 是没用的。
优化 2
最重要的优化。如果我们并未塞下所有小猫,而当前所开的缆车数已经大于等于之前搜到过的可行的答案了,我们无论如何继续操作都不会得到比先前更少的缆车数,即无法更新答案。此时直接回溯停止搜索即可。
就像是把搜索树劈成好几瓣,优化了很多的冗余搜索。
优化 2 是最关键的优化,带上即可通过。笔者带着优化 2 不带优化 1 的代码跑了 101ms,优化 1 带上后跑了 17ms。
AC CODE
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 20;
int n, w, a[maxn], car[maxn], ans = 0x3f3f3f3f;
void dfs(int x, int num) {
if (x == n + 1) {
ans = min(ans, num);
return;
}
if (num >= ans) return;
car[num + 1] = w - a[x]; dfs(x + 1, num + 1); car[num + 1] = w;
for (int i = 1; i <= num; ++i) {
if (car[i] >= a[x]) car[i] -= a[x], dfs(x + 1, num), car[i] += a[x];
}
}
inline bool cmp(int a, int b) { return a > b; }
int main() {
scanf("%d%d", &n, &w);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), car[i] = w;
sort(a + 1, a + 1 + n, cmp);
car[1] = w - a[1]; dfs(2, 1);
printf("%d", ans);
return 0;
}
/*
18 100000000
18381246
29249683
12495474
24844134
96242521
67846996
945213
27675252
58653213
12062801
4830609
83790642
10682393
27267295
60527976
8881456
3916444
32450339
*/