首页 > > 程序设计 > C/C++ >

小猫爬山

2018-12-25 08:22:23来源：博客园阅读 ()

2201 小猫爬山 0x20「搜索」例题

背景

Freda和rainbow饲养了N只小猫，这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。

描述

Freda和rainbow只好花钱让它们坐索道下山。索道上的缆车最大承重量为W，而N只小猫的重量分别是C1、C2……CN。当然，每辆缆车上的小猫的重量之和不能超过W。每租用一辆缆车，Freda和rainbow就要付1美元，所以他们想知道，最少需要付多少美元才能把这N只小猫都运送下山？

输入格式

第一行包含两个用空格隔开的整数，N和W。
接下来N行每行一个整数，其中第i+1行的整数表示第i只小猫的重量Ci。

输出格式

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

样例输入

样例输出

数据范围与约定

对于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("%d\n",ans);
44     return 0;
45 }