2201 小猫爬山 0x20「搜索」例题
背景
Freda和rainbow饲养了N只小猫，这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。
描述
Freda和rainbow只好花钱让它们坐索道下山。索道上的缆车最大承重量为W，而N只小猫的重量分别是C1、C2……CN。当然，每辆缆车上的小猫的重量之和不能超过W。每租用一辆缆车，Freda和rainbow就要付1美元，所以他们想知道，最少需要付多少美元才能把这N只小猫都运送下山？
输入格式
第一行包含两个用空格隔开的整数，N和W。
接下来N行每行一个整数，其中第i+1行的整数表示第i只小猫的重量Ci。
输出格式
输出一个整数，最少需要多少美元，也就是最少需要多少辆缆车。
样例输入
5 1996 1 2 1994 12 29
样例输出
2
数据范围与约定
- 对于100%的数据，1<=N<=18，1<=Ci<=W<=10^8。
思路：可以用深度优先搜索解决这道题，我们可以尝试把小猫分配到一辆已经租用的缆车上，或者，用另外的一辆缆车，dfs（now，cnt）现在处理第now只猫，前面的now-1
只已经分配好了，目前已经租用了cnt辆缆车。
1.尝试把第now只小猫分配到（1-cnt ）其第i辆缆车上，如果能分配，对应的缆车cab[i]累加小猫的重量，然后递归dfs（now+1，cnt）；
2.尝试用新的缆车，也就令cab[cnt+1]=a[now],递归dfs（now+1，cnt+1）；
这道题必须要剪枝才能过，我们搜索到cnt>=ans，在当前分枝就可以回溯了。除此之外，重量大的 猫更难运输，所以我们可以优先搜索重量较大的猫，减少搜索树的“分支”的数量；
1 #include<stdio.h> 2 #include<algorithm> 3 #include<stdlib.h> 4 using namespace std; 5 bool cmp(int x,int y) 6 { 7 return x>y; 8 } 9 const int maxn=100; 10 int n,w,cnt,cab[maxn],a[maxn],ans; 11 void dfs(int now,int cnt) 12 { 13 if(cnt>=ans) 14 return ; 15 if(now==n+1) 16 { 17 ans=min(ans,cnt); 18 return ; 19 } 20 for(int i=1; i<=cnt; i++) 21 { 22 if(cab[i]+a[now]<=w) 23 { 24 cab[i]+=a[now]; ///这个缆车装这只猫 25 dfs(now+1,cnt); 26 cab[i]-=a[now];///不装 27 } 28 } 29 ///前面所以的缆车都不装，用新的缆车来装 30 cab[cnt+1]=a[now]; 31 dfs(now+1,cnt+1); 32 cab[cnt+1]=0; 33 } 34 int main() 35 { 36 37 scanf("%d%d",&n,&w); 38 for(int i=1; i<=n; i++) 39 scanf("%d",&a[i]); 40 sort(a,a+n,cmp); 41 ans=n; 42 dfs(0,0); 43 printf("%dn",ans); 44 return 0; 45 }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
