小猫爬山 搜索剪枝

题目链接

https://www.acwing.com/problem/content/description/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≤10^8

输入样例：

5 1996 1 2 1994 12 29

输出样例：

2

 题解：

       dfs（v,sum）表示处理第v只小猫的分配过程（前v-1只已经装载），并且已经租用了sum辆车，对于已经租用的这sum辆缆车的当前搭载量，用全局数组cnt[]来记录

      1.尝试把第v只小猫分配到已经租用的第i（1<=i<=sum）辆缆车上。如果第i辆缆车还装得下，我们就在cnt[i]中累加a[v],然后递归dfs（v+1,sum）。

     2，尝试新租一辆缆车来安置这只小猫，也就是令cnt[sum+1]=a[v]，然后递归dfs(v+1,sum+1)

    当now=n+1时，说明搜索到了递归边界，此时可以用sum更新答案。

  两种优化方式：

  1.dfs（v,sum） 如果当前sum已经大于或等于ans，那么结束当前分支。因为当前分支走到最后肯定大于或等于ans，没必要走。

  2.优化搜索顺序。将小猫按照重量从大到小排序。优先搜索重量较大的小猫，可以减少搜索树的分支的数量。

代码：

#include<bits/stdc++.h> using namespace std; const int maxn=20; int a[maxn]; int cnt[maxn]; int ans; int n,m; void dfs(int v,int sum){ if(sum>=ans) return; //剪枝 if(v==n+1){ ans=sum; //因为有剪枝1，所以当前sum一定小于ans return; } for(int i=1;i<=sum;i++){ //搜索方式1 if(cnt[i]+a[v]<=m){ cnt[i]+=a[v]; dfs(v+1,sum); cnt[i]-=a[v]; //回溯 } } //搜索方式2 cnt[sum+1]=a[v]; dfs(v+1,sum+1); cnt[sum+1]=0; //回溯 } int main(){ cin>>n>>m; ans=n; //最坏的情况下每辆车搭载一只小猫。需要n辆缆车 for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n,greater<int>()); //优化搜索顺序 dfs(1,0); cout<<ans<<endl; return 0; }