c/c++语言开发共享小猫爬山

2201 小猫爬山 0x20「搜索」例题 背景 Freda和rainbow饲养了N只小猫,这天,小猫们要去爬山。经历了千辛万苦,小猫们终于爬上了山顶,但是疲倦的它们再也不想徒步走下山了(呜咕>_<)。 描述 Freda和rainbow只好花钱让它们坐索道下山。索道上的缆车最大承重量为W,而N只小猫的 …


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

背景

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

描述

freda和rainbow只好花钱让它们坐索道下山。索道上的缆车最大承重量为w,而n只小猫的重量分别是c1、c2&hellip;…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,在当前分枝就可以回溯了。除此之外,重量大的 猫更难运输,所以我们可以优先搜索重量较大的猫,减少搜索树的“分支”的数量;

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ctvol.com/c-cdevelopment/605799.html

(0)
上一篇 2021年5月13日
下一篇 2021年5月13日

精彩推荐