当前位置: 首页 > article >正文

算法刷题-小猫爬山

本题来源165. 小猫爬山 - AcWing题库

翰翰和达达饲养了 NN 只小猫,这天,小猫们要去爬山。

经历了千辛万苦,小猫们终于爬上了山顶,但是疲倦的它们再也不想徒步走下山了(呜咕>_<)。

翰翰和达达只好花钱让它们坐索道下山。

索道上的缆车最大承重量为 W,而 N 只小猫的重量分别是 C1、C2……CN。

当然,每辆缆车上的小猫的重量之和不能超过 W。

每租用一辆缆车,翰翰和达达就要付 1 美元,所以他们想知道,最少需要付多少美元才能把这 N只小猫都运送下山?

输入格式

第 1 行:包含两个用空格隔开的整数,N 和 W。

第 2..N+1行:每行一个整数,其中第 i+1行的整数表示第 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}。

注意,这里我们是进行了两层嵌套的枚举。

我们先不要想搜索过程中哪些可行,哪些不可行,我们先把所有的都枚举出来(搭建好这个结构再进行剪枝)

#include<iostream>
#include<algorithm>
#include<string>
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_car>=ans) return;  //没有这个会T
    if(num_cat>=n){//当枚举完小猫,这一个深度(方案)完成
        ans = min(ans,counter_car);//只有这个方案数小时,才更新
        return ;//方案完成要返回
    }
    for(int i=0;i<counter_car;i++){//这里枚举到这只小猫了,就要从之前已经装车的上面依次枚举每辆车
        if(car[i]+cat[num_cat]<=W){//只有小猫可以放入这辆车,才进行操作
            car[i]+=cat[num_cat];  //选择的车重量加
            dfs(num_cat+1,counter_car);        //开始枚举下一只小猫,但是总车的数量不变
            car[i]-=cat[num_cat];  //恢复现场,看一下下一辆车
        }
    }
    
    car[counter_car] = cat[num_cat];//新开一个车
    dfs(num_cat+1,counter_car+1);
    car[counter_car]=0;//恢复现场
    }

int main(){
    cin>>n>>W;
    for(int i=0;i<n;i++) cin>>cat[i];
    sort(cat,cat+n);//从小到大排序
    reverse(cat,cat+n);//反转顺序
    
    dfs(0,0);//当前从第0只猫开始搜,当前使用的车的数量是0
    
    cout<<ans<<endl;
    
    
    
    
    return 0;
}

总结一下这类将n个物品放入有限制的容器中,并且求最小容器数的解法:

枚举这n个物品,枚举到第i个物品时,先给第i个物品选择要放入的地方(这个地方可以是已经有的,也可以是新建的。然后再去枚举下一个物品。)。在这其中,如何来“标记”已经选好的地方呢?可以将“已经使用的数量”作为参数,放入DFS的参数中。


http://www.kler.cn/a/372235.html

相关文章:

  • ppt设计软件哪个好?这5个在线ppt工具不容错过!
  • 计算机视觉-对极几何
  • 字符串-05-字符串合并处理
  • Xcode 16.1 (16B40) 发布下载 - Apple 平台 IDE
  • Ubuntu 20.04 安装 OpenCV 和 OpenCV_contrib 教程
  • Git相关介绍
  • 从0开始搭建一个生产级SpringBoot2.0.X项目(二)SpringBoot应用连接数据库集成mybatis-plus
  • ElasticSearch - Bucket Script 使用指南
  • 三菱FX5U PLC使用SD存储卡固件更新的方法
  • python实现excel数据导入数据库
  • 频率限制:WAF保护网站免受恶意攻击的关键功能
  • Yolov5网络架构分析以及训练图解
  • Kafka如何控制消费的位置?
  • 数据驱动业务中的BDS对账班牛返款表集成方案
  • 前端开发设计模式——观察者模式
  • 论文题目:深度学习在自然语言处理中的应用研究
  • 开源FluentFTP实操,操控FTP文件
  • SpringBoot最佳实践之 - 使用AOP记录操作日志
  • 电子电气架构 --- 汽车以太网概述
  • 论文翻译:ICLR 2024.DETECTING PRETRAINING DATA FROM LARGE LANGUAGE MODELS
  • 免费PDF页面提取小工具
  • 《自动驾驶技术的深度思考:安全与伦理的挑战》
  • ubuntu22安装搜狗输入法不能输入中文
  • Java 代码优化 修饰器模式(Decorator Pattern)
  • 搭建 mongodb 副本集,很详细
  • 【MySQL】C语言连接MySQL数据库3——事务操作和错误处理API