<—点个赞吧QwQ

宣传一下算法提高课整理

翰翰和达达饲养了 $N$ 只小猫，这天，小猫们要去爬山。

经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。

翰翰和达达只好花钱让它们坐索道下山。

索道上的缆车最大承重量为 $W$，而 $N$ 只小猫的重量分别是 $C_1、C_2……C_N$。

当然，每辆缆车上的小猫的重量之和不能超过 $W$。

每租用一辆缆车，翰翰和达达就要付 $1$ 美元，所以他们想知道，最少需要付多少美元才能把这 $N$ 只小猫都运送下山？

输入格式

第 $1$ 行：包含两个用空格隔开的整数，$N$ 和 $W$。

第 $2..N+1$ 行：每行一个整数，其中第 $i+1$ 行的整数表示第 $i$ 只小猫的重量 $C_i$。

输出格式

输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。

数据范围

$1 \le N \le 18$,
$1 \le C_i \le W \le 10^8$

输入样例：

5 1996
1
2
1994
12
29

输出样例：

2

思路

这里和上一题的思路类似，因为都有以下两种方法：

1. 放到原有的组中
2. 新开一个组

但是这题数据量较大，我们需要剪枝。剪枝就是把搜索树的多余的枝条减去。

那我们可以怎么剪枝呢？
其实有以下基本剪枝方法：

1. 优化搜索顺序$~\color{green}✔$
   • 就是换个搜索顺序，但效率不同，也就是优先搜枝条少的搜索子树
   • 这里我们可以优先搜索质量重的猫，所以我们可以把所有的猫按重量从大到小排序
2. 排除等效冗余$~\color{red}✖$
   • 因为整棵搜索树都会搜到，所以不能排除等效冗余
3. 可行性剪枝$~\color{green}✔$
   • 如果当前位置放了一个猫就会超重，那么就不要放
4. 最优化剪枝$~\color{green}✔$
   • 如果当前答案不优于最优解，那么就不要搜

最后照着思路写即可。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 20;
int n,m;
int a[N],sum[N];
int ans = 2e9;
void dfs (int u,int res) {
    if (res >= ans) return ;
    if (u > n) {
        ans = min (ans,res);
        return ;
    }
    for (int i = 1;i <= res;i++) {
        if (sum[i] + a[u] <= m) {
            sum[i] += a[u];
            dfs (u + 1,res);
            sum[i] -= a[u];
        }
    }
    sum[res + 1] = a[u];
    dfs (u + 1,res + 1);
    sum[res + 1] = 0;
}
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) cin >> a[i];
    sort (a + 1,a + 1 + n,[](int p,int q) {
        return p > q;
    });
    dfs (1,1);
    cout << ans << endl;
    return 0;
}