做公司网站的总结,网站设计方案大全,中国建造师网官网个人入口,网站建设与实践心得体会本题来源165. 小猫爬山 - AcWing题库
翰翰和达达饲养了 NN 只小猫#xff0c;这天#xff0c;小猫们要去爬山。
经历了千辛万苦#xff0c;小猫们终于爬上了山顶#xff0c;但是疲倦的它们再也不想徒步走下山了#xff08;呜咕_#xff09;。
翰翰和达达只好花…本题来源165. 小猫爬山 - AcWing题库
翰翰和达达饲养了 NN 只小猫这天小猫们要去爬山。
经历了千辛万苦小猫们终于爬上了山顶但是疲倦的它们再也不想徒步走下山了呜咕_。
翰翰和达达只好花钱让它们坐索道下山。
索道上的缆车最大承重量为 W而 N 只小猫的重量分别是 C1、C2……CN。
当然每辆缆车上的小猫的重量之和不能超过 W。
每租用一辆缆车翰翰和达达就要付 1 美元所以他们想知道最少需要付多少美元才能把这 N只小猫都运送下山
输入格式
第 1 行包含两个用空格隔开的整数N 和 W。
第 2..N1行每行一个整数其中第 i1行的整数表示第 i 只小猫的重量 Ci。
输出格式
输出一个整数表示最少需要多少美元也就是最少需要多少辆缆车。
数据范围
1≤N≤18, 1≤Ci≤W≤10^8
输入样例
5 1996
1
2
1994
12
29输出样例
2
我们想一下如若使用DFS进行解答暴力解答。
其实许多类似的题难的地方不在于DFS本身而在于题目的转化即要想一种枚举的策略或者说一种树形枚举的结构能将所有可能性都考虑到。
首先没有任何想法的时候不妨从问题最表面的地方出发问题中有小猫的体重还问我们需要的小车的数量。--那么我们可以尝试一下从这个找到切入点比如枚举每一个小猫或者枚举每一个小车
这里我们来“试错”一下。
假如我们要枚举小猫。
我们要如何枚举呢
那肯定是要一个一个枚举啊。
找到一个小猫后面需要干什么这里从开始想不好想。从结束想也不好想那么不妨从中间开始想但是这样的话我们需要假设之前的已经选好了几个小车了比如{猫1猫3}、{猫2猫4}。现在到“猫5”了该如何操作呢
假设我们已经选到“猫5”了那么很自然我们要从组1到组2一个一个枚举能不能装入如果这两个组都枚举完了的话那就要新建一个组了{猫1猫3}、{猫2猫4}、{猫5}。
注意这里我们是进行了两层嵌套的枚举。
我们先不要想搜索过程中哪些可行哪些不可行我们先把所有的都枚举出来搭建好这个结构再进行剪枝
#includeiostream
#includealgorithm
#includestring
using namespace std;
const int N 19;
int car[N];//这里存放每个车已经有多少重量了因为题目不要求输出方案所以不需要单独存储每个车上有哪个具体的小猫
int cat[N];//每个小猫的重量
int n,W;
int ans N;void dfs(int num_cat,int counter_car){// num_cat:当前枚举到第几只猫counter_car:已经使用几辆车了if(counter_carans) return; //没有这个会Tif(num_catn){//当枚举完小猫这一个深度方案完成ans min(ans,counter_car);//只有这个方案数小时才更新return ;//方案完成要返回}for(int i0;icounter_car;i){//这里枚举到这只小猫了就要从之前已经装车的上面依次枚举每辆车if(car[i]cat[num_cat]W){//只有小猫可以放入这辆车才进行操作car[i]cat[num_cat]; //选择的车重量加dfs(num_cat1,counter_car); //开始枚举下一只小猫但是总车的数量不变car[i]-cat[num_cat]; //恢复现场看一下下一辆车}}car[counter_car] cat[num_cat];//新开一个车dfs(num_cat1,counter_car1);car[counter_car]0;//恢复现场}int main(){cinnW;for(int i0;in;i) cincat[i];sort(cat,catn);//从小到大排序reverse(cat,catn);//反转顺序dfs(0,0);//当前从第0只猫开始搜当前使用的车的数量是0coutansendl;return 0;
}
总结一下这类将n个物品放入有限制的容器中并且求最小容器数的解法
枚举这n个物品枚举到第i个物品时先给第i个物品选择要放入的地方这个地方可以是已经有的也可以是新建的。然后再去枚举下一个物品。。在这其中如何来“标记”已经选好的地方呢可以将“已经使用的数量”作为参数放入DFS的参数中。
