原题链接：https://www.acwing.com/problem/content/167/

题目描述

翰翰和达达饲养了N只小猫，这天，小猫们要去爬山。 经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。 翰翰和达达只好花钱让它们坐索道下山。 索道上的缆车最大承重量为W，而N只小猫的重量分别是C1、C2……CN。 当然，每辆缆车上的小猫的重量之和不能超过W。 每租用一辆缆车，翰翰和达达就要付1美元，所以他们想知道，最少需要付多少美元才能把这N只小猫都运送下山？ 输入格式 第1行：包含两个用空格隔开的整数，N和W。 第2…N+1行：每行一个整数，其中第i+1行的整数表示第i只小猫的重量Ci。 输出格式 输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。 数据范围 1≤N≤18, 1≤Ci≤W≤108 输入样例： 5 1996 1 2 1994 12 29 输出样例： 2

题解

1.搜索顺序：枚举每一只猫，每一只猫可以放到已有的不同的篮子里，或者重新租一个篮子。 2.剪枝：可以对猫按体重从大到小排序，重的猫可以选择的篮子少，递归分支减少。

#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 20; int a[N]; int n, m; int ans = N; int s[N]; void dfs(int u, int k) { if(k > ans) return; //剪枝1 if(u == n) { ans = k; return; } for(int i = 0; i < k; i++) { if(a[u] + s[i] <= m) { s[i] += a[u]; dfs(u + 1, k); s[i] -= a[u]; } } s[k] += a[u]; dfs(u + 1, k + 1); s[k] = 0; } int main() { cin >> n >> m; for(int i = 0; i < n; i++) cin >> a[i]; //剪枝2. sort(a, a + n); reverse(a, a + n); dfs(0, 0); cout << ans << endl; return 0; }