165. 小猫爬山(DFS之剪枝与优化)
165. 小猫爬山 - AcWing题库
翰翰和达达饲养了 N 只小猫,这天,小猫们要去爬山。
经历了千辛万苦,小猫们终于爬上了山顶,但是疲倦的它们再也不想徒步走下山了(呜咕>_<)。
翰翰和达达只好花钱让它们坐索道下山。
索道上的缆车最大承重量为 W,而 N 只小猫的重量分别是 C1、C2……Cn。
当然,每辆缆车上的小猫的重量之和不能超过 W。
每租用一辆缆车,翰翰和达达就要付 1 美元,所以他们想知道,最少需要付多少美元才能把这 N 只小猫都运送下山?
输入格式
第 1 行:包含两个用空格隔开的整数,N 和 W。
第 2..N+1 行:每行一个整数,其中第 i+1 行的整数表示第 i 只小猫的重量 Ci。
输出格式
输出一个整数,表示最少需要多少美元,也就是最少需要多少辆缆车。
数据范围
1≤N≤18
1≤Ci≤W≤108
输入样例:
5 1996
1
2
1994
12
29
输出样例:
2
解析 :
DFS之剪枝与优化主要方法:
1.优化搜索顺序:大部分情况下,我们应该优先搜索分支较少的节点
2.排除等效冗余
3.可行性剪枝
4.最优性剪枝
5.记忆化搜索(dp)
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N = 20;
int n, w;
int cr[N], sum[N];
int ans;int cmp(const int& a, const int& b) {return a > b;
}void dfs(int u, int k) {//最优性剪枝if (k >= ans)return;if (u > n) {ans = k;return;}for (int i = 1; i <= k; i++) {if (sum[i] + cr[u] <= w) {//可行性剪枝sum[i] += cr[u];dfs(u + 1, k);sum[i] -= cr[u];//恢复现场}}sum[k + 1] = cr[u];dfs(u + 1, k + 1);
}int main() {cin >> n >> w;for (int i = 1; i <= n; i++) {scanf("%d", &cr[i]);}//优化搜索顺序sort(cr + 1, cr + 1 + n, cmp);ans = n;dfs(1, 1);cout << ans << endl;return 0;
}
相关文章:
165. 小猫爬山(DFS之剪枝与优化)
165. 小猫爬山 - AcWing题库 翰翰和达达饲养了 N 只小猫,这天,小猫们要去爬山。 经历了千辛万苦,小猫们终于爬上了山顶,但是疲倦的它们再也不想徒步走下山了(呜咕>_<)。 翰翰和达达只好花钱让它们…...
【Linux系统基础】(6)在Linux上大数据NoSQL数据库HBase集群部署、分布式内存计算Spark环境及Flink环境部署详细教程
大数据NoSQL数据库HBase集群部署 简介 HBase 是一种分布式、可扩展、支持海量数据存储的 NoSQL 数据库。 和Redis一样,HBase是一款KeyValue型存储的数据库。 不过和Redis设计方向不同 Redis设计为少量数据,超快检索HBase设计为海量数据,…...
多维时序 | MATLAB实CNN-BiGRU-Mutilhead-Attention卷积网络结合双向门控循环单元网络融合多头注意力机制多变量时间序列预测
多维时序 | MATLAB实现CNN-BiGRU-Mutilhead-Attention卷积网络结合双向门控循环单元网络融合多头注意力机制多变量时间序列预测 目录 多维时序 | MATLAB实现CNN-BiGRU-Mutilhead-Attention卷积网络结合双向门控循环单元网络融合多头注意力机制多变量时间序列预测预测效果基本介…...
vs快捷键
ctrlMo 折叠代码块 ctrlML 打开代码块...
linux 内核时间计量方法
定时器中断由系统定时硬件以规律地间隔产生; 这个间隔在启动时由内核根据 HZ 值来编 程, HZ 是一个体系依赖的值, 在 <linux/param.h>中定义或者它所包含的一个子平台文 件中. 在发布的内核源码中的缺省值在真实硬件上从 50 到 1200 嘀哒每秒, 在软件模拟 器中往下到 24.…...
循环神经网络中的梯度消失或梯度爆炸问题产生原因分析(二)
上一篇中讨论了一般性的原则,这里我们具体讨论通过时间反向传播(backpropagation through time,BPTT)的细节。我们将展示目标函数对于所有模型参数的梯度计算方法。 出于简单的目的,我们以一个没有偏置参数的循环神经…...
JWT signature does not match locally computed signature
1. 问题背景 最近在协助团队小盆友调试一个验签问题,结果还“节外生枝”了,原来不是签名过程的问题,是token的问题。 当你看到“JWT signature does not match locally computed signature. JWT validity cannot be asserted and should not…...
vitepress项目使用github的action自动部署到github-pages中,理论上可以通用所有
使用github的action自动部署到github-pages中 创建部署的deploy.yml文件,在项目的根目录下面 .github\workflows\deploy.yml 完整的代码:使用的是pnpm进行依赖安装。 name: 部署VitePresson:push:branches:- docs # 这段是在推送到 docs 分支时触发该…...
Python爬虫---解析---JSONPath
Xpath可以解析本地文件和服务器响应的文件,JSONPath只能解析本地文件 1. 安装jsonpath:pip install jsonpath 注意:需要安装在python解释器相同的位置,例如:D:\Program Files\Python3.11.4\Scripts 2. 使用步骤 2.1 导入&…...
路由器介绍和命令操作
先来回顾一下上次的内容: ip地址就是由32位二进制数组 二进位数就是只有数字0和1组成 网络位:类似于区号,表示区域作用 主机位:类似于号码,表示区域中编号 网络名称:网络位不变,主机位全为0 …...
Hadoop——分布式计算
一、分布式计算概述 1. 什么是计算、分布式计算? 计算:对数据进行处理,使用统计分析等手段得到需要的结果分布式计算:多台服务器协同工作,共同完成一个计算任务2. 分布式计算常见的2种工作模式分散->汇总 (MapReduce就是这种模式)将数据分片,多台服务器各自负责一…...
LaTeX引用参考文献 | Texstudio引用参考文献
图片版教程: 文字版教程: ref.bib里面写参考的文献,ref.bib和document.tex要挨着放,同一个目录里面. 解析一下bib文件格式:aboyeji2023effect是引用文献的关键字,需要在正文document.tex里面使用\cite指令…...
如何在Go中使用模板
引言 您是否需要以格式良好的输出、文本报告或HTML页面呈现一些数据?你可以使用Go模板来做到这一点。任何Go程序都可以使用text/template或html/template包(两者都包含在Go标准库中)来整齐地显示数据。 这两个包都允许你编写文本模板并将数据传递给它们,以按你喜欢的格式呈…...
云原生之深入解析基于FunctionGraph在Serverless领域的FinOps的探索和实践
一、背景 Serverless 精确到毫秒级的按用付费模式使得用户不再需要为资源的空闲时间付费。然而,对于给定的某个应用函数,由于影响其计费成本的因素并不唯一,使得用户对函数运行期间的总计费进行精确的事先估计变成了一项困难的工作。以传统云…...
电子电器架构(E/E)演化 —— 主流主机厂域集中架构概述
电子电器架构(E/E)演化 —— 主流主机厂域集中架构概述 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。…...
Python常用的几个函数
print()函数:用于打印输出信息到控制台。 input()函数:用于从控制台获取用户输入。 len()函数:用于获取字符串、列表、元组、字典等对象的长度。 range()函数:用于生成一个整数序列,常用于循环中。 type()函数&…...
【Linux系统基础】(2)在Linux上部署MySQL、RabbitMQ、ElasticSearch等各类软件
实战章节:在Linux上部署各类软件 前言 为什么学习各类软件在Linux上的部署 在前面,我们学习了许多的Linux命令和高级技巧,这些知识点比较零散,同学们跟随着课程的内容进行练习虽然可以基础掌握这些命令和技巧的使用,…...
HarmonyOS4.0系统性深入开发01应用模型的构成要素
应用模型的构成要素 应用模型是HarmonyOS为开发者提供的应用程序所需能力的抽象提炼,它提供了应用程序必备的组件和运行机制。有了应用模型,开发者可以基于一套统一的模型进行应用开发,使应用开发更简单、高效。 HarmonyOS应用模型的构成要…...
线下终端门店调研包含哪些内容
品牌渠道一般分为线上和线下,线上的价格、促销信息、店铺优惠机制等都可以通过登录查看,但是线下门店的数据则需要进店巡查,否则无法得到真实的店铺销售数据,当然也有品牌是靠线下的业务团队报备机制获得这些信息,但是…...
倾斜摄影三维模型数据在行业应用分析
倾斜摄影三维模型数据在行业应用分析 倾斜摄影三维模型数据是一种重要的地理信息资源,可以广泛应用于各个行业和场景,以解决不同领域的问题。以下将详细探讨几个典型的行业或场景,它们利用倾斜摄影三维模型数据解决问题的应用。 1、地理测绘…...
无需配置环境!MinerU镜像一键部署,即刻体验智能文档解析
无需配置环境!MinerU镜像一键部署,即刻体验智能文档解析 1. 为什么选择智能文档解析? 在日常办公和学习中,我们经常需要处理各种文档资料:PDF报告、扫描合同、学术论文、财务报表等。传统方式要么需要手动输入&#…...
GitHub下载加速终极指南:3分钟让你的克隆速度提升100倍
GitHub下载加速终极指南:3分钟让你的克隆速度提升100倍 【免费下载链接】Fast-GitHub 国内Github下载很慢,用上了这个插件后,下载速度嗖嗖嗖的~! 项目地址: https://gitcode.com/gh_mirrors/fa/Fast-GitHub 如果你经常需要…...
零基础玩转像素心智:手把手教你用情绪解码器分析用户评论
零基础玩转像素心智:手把手教你用情绪解码器分析用户评论 1. 认识像素心智情绪解码器 1.1 什么是情绪解码器 像素心智情绪解码器(Pixel Mind Decoder)是一款基于M2LOrder核心引擎构建的AI情绪识别工具。它将复杂的自然语言处理技术封装在一个充满复古游戏风格的1…...
手把手教你用TI F28P65X开发板实现LED定时闪烁(基于CPU Timer2,含完整源码)
从零玩转TI F28P65X开发板:CPU Timer2实现可调频LED闪烁实战指南 刚拿到TI F28P65X开发板时,面对密密麻麻的引脚和复杂的开发环境,很多嵌入式新手会感到无从下手。本文将带你用最直观的方式,通过控制LED闪烁这个经典入门项目&…...
rk3576 点亮 LCD(mipi)
rk3576 适配 mipi 屏 瑞芯微 RK3576 是一款面向中高端 AIoT 市场的 SoC,其 MIPI DSI (Display Serial Interface) 接口在性能和灵活性上相比前代(如 RK3399/RK3568)有显著提升,特别是在物理层协议的支持上更加现代化。相比RK3399 RK3568的mipi 接口少了 8lane,但是RK3576…...
Zotero中文文献管理终极指南:茉莉花插件一键解决三大痛点
Zotero中文文献管理终极指南:茉莉花插件一键解决三大痛点 【免费下载链接】jasminum A Zotero add-on to retrive CNKI meta data. 一个简单的Zotero 插件,用于识别中文元数据 项目地址: https://gitcode.com/gh_mirrors/ja/jasminum 如果你正在使…...
Cosmos-Reason1-7B部署教程:Docker镜像免配置+7860端口快速启用
Cosmos-Reason1-7B部署教程:Docker镜像免配置7860端口快速启用 1. 项目概述 Cosmos-Reason1-7B是NVIDIA推出的7B参数多模态视觉语言模型(VLM),专注于物理理解和思维链推理能力。作为Cosmos世界基础模型平台的核心组件,它能够处理图像和视频…...
如何通过技术优化提升Element Plus开发效率
如何通过技术优化提升Element Plus开发效率 【免费下载链接】element-plus 🎉 A Vue.js 3 UI Library made by Element team 项目地址: https://gitcode.com/GitHub_Trending/el/element-plus 在前端开发过程中,Element Plus作为一款基于Vue.js 3…...
Ceph存储集群搭建:如何选择RAID卡模式(HBA vs IT vs non-RAID)
Ceph存储集群搭建:RAID卡模式选择与性能优化实战指南 在构建企业级Ceph存储集群时,硬件配置的每一个细节都可能成为性能瓶颈或稳定性隐患。其中,RAID控制器的工作模式选择——HBA、IT与non-RAID之间的差异,往往被许多初次部署Ceph…...
MedGemma-X智能助手实测:像住院总医师一样分析X光片
MedGemma-X智能助手实测:像住院总医师一样分析X光片 1. 重新定义影像诊断:从工具到助手 在放射科的日常工作中,我们习惯了与各种CAD(计算机辅助诊断)系统打交道。它们像精确但沉默的尺子,能在图像上标出可…...
