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
思路：可以用深度优先搜索解决这道题，我们可以尝试把小猫分配到一辆已经租用的缆车上，或者，用另外的一辆缆车，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，在当前分枝就可以回溯了。除此之外，重量大的 猫更难运输，所以我们可以优先搜索重量较大的猫，减少搜索树的“分支”的数量；
如对本文有疑问， 点击进行留言回复！！
2020年 浙江工业大学计算机科学与技术学硕 初试复试经验帖
详细分解VMware Workstation Pro 15.5 新建虚拟机以及安装 Ubuntu 20.04（上）
matlab已知随机样本求总体均值与方差的矩估计值(例子应用)
我要评论
网友评论