小猫爬山

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

新老客户大回馈,云服务器低至5折

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

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Java中Arrays作用

下一篇:POJ 2983 M &#215; N Puzzle