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

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 只小猫&#xff0c;这天&#xff0c;小猫们要去爬山。 经历了千辛万苦&#xff0c;小猫们终于爬上了山顶&#xff0c;但是疲倦的它们再也不想徒步走下山了&#xff08;呜咕>_<&#xff09;。 翰翰和达达只好花钱让它们…...

【Linux系统基础】(6)在Linux上大数据NoSQL数据库HBase集群部署、分布式内存计算Spark环境及Flink环境部署详细教程

大数据NoSQL数据库HBase集群部署 简介 HBase 是一种分布式、可扩展、支持海量数据存储的 NoSQL 数据库。 和Redis一样&#xff0c;HBase是一款KeyValue型存储的数据库。 不过和Redis设计方向不同 Redis设计为少量数据&#xff0c;超快检索HBase设计为海量数据&#xff0c;…...

多维时序 | 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.…...

循环神经网络中的梯度消失或梯度爆炸问题产生原因分析(二)

上一篇中讨论了一般性的原则&#xff0c;这里我们具体讨论通过时间反向传播&#xff08;backpropagation through time&#xff0c;BPTT&#xff09;的细节。我们将展示目标函数对于所有模型参数的梯度计算方法。 出于简单的目的&#xff0c;我们以一个没有偏置参数的循环神经…...

JWT signature does not match locally computed signature

1. 问题背景 最近在协助团队小盆友调试一个验签问题&#xff0c;结果还“节外生枝”了&#xff0c;原来不是签名过程的问题&#xff0c;是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文件&#xff0c;在项目的根目录下面 .github\workflows\deploy.yml 完整的代码&#xff1a;使用的是pnpm进行依赖安装。 name: 部署VitePresson:push:branches:- docs # 这段是在推送到 docs 分支时触发该…...

Python爬虫---解析---JSONPath

Xpath可以解析本地文件和服务器响应的文件&#xff0c;JSONPath只能解析本地文件 1. 安装jsonpath&#xff1a;pip install jsonpath 注意&#xff1a;需要安装在python解释器相同的位置,例如&#xff1a;D:\Program Files\Python3.11.4\Scripts 2. 使用步骤 2.1 导入&…...

路由器介绍和命令操作

先来回顾一下上次的内容&#xff1a; ip地址就是由32位二进制数组 二进位数就是只有数字0和1组成 网络位&#xff1a;类似于区号&#xff0c;表示区域作用 主机位&#xff1a;类似于号码&#xff0c;表示区域中编号 网络名称&#xff1a;网络位不变&#xff0c;主机位全为0 …...

Hadoop——分布式计算

一、分布式计算概述 1. 什么是计算、分布式计算? 计算:对数据进行处理,使用统计分析等手段得到需要的结果分布式计算:多台服务器协同工作,共同完成一个计算任务2. 分布式计算常见的2种工作模式分散->汇总 (MapReduce就是这种模式)将数据分片,多台服务器各自负责一…...

LaTeX引用参考文献 | Texstudio引用参考文献

图片版教程&#xff1a; 文字版教程&#xff1a; ref.bib里面写参考的文献&#xff0c;ref.bib和document.tex要挨着放&#xff0c;同一个目录里面. 解析一下bib文件格式&#xff1a;aboyeji2023effect是引用文献的关键字&#xff0c;需要在正文document.tex里面使用\cite指令…...

如何在Go中使用模板

引言 您是否需要以格式良好的输出、文本报告或HTML页面呈现一些数据?你可以使用Go模板来做到这一点。任何Go程序都可以使用text/template或html/template包(两者都包含在Go标准库中)来整齐地显示数据。 这两个包都允许你编写文本模板并将数据传递给它们,以按你喜欢的格式呈…...

云原生之深入解析基于FunctionGraph在Serverless领域的FinOps的探索和实践

一、背景 Serverless 精确到毫秒级的按用付费模式使得用户不再需要为资源的空闲时间付费。然而&#xff0c;对于给定的某个应用函数&#xff0c;由于影响其计费成本的因素并不唯一&#xff0c;使得用户对函数运行期间的总计费进行精确的事先估计变成了一项困难的工作。以传统云…...

电子电器架构(E/E)演化 —— 主流主机厂域集中架构概述

电子电器架构(E/E)演化 —— 主流主机厂域集中架构概述 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。…...

Python常用的几个函数

print()函数&#xff1a;用于打印输出信息到控制台。 input()函数&#xff1a;用于从控制台获取用户输入。 len()函数&#xff1a;用于获取字符串、列表、元组、字典等对象的长度。 range()函数&#xff1a;用于生成一个整数序列&#xff0c;常用于循环中。 type()函数&…...

【Linux系统基础】(2)在Linux上部署MySQL、RabbitMQ、ElasticSearch等各类软件

实战章节&#xff1a;在Linux上部署各类软件 前言 为什么学习各类软件在Linux上的部署 在前面&#xff0c;我们学习了许多的Linux命令和高级技巧&#xff0c;这些知识点比较零散&#xff0c;同学们跟随着课程的内容进行练习虽然可以基础掌握这些命令和技巧的使用&#xff0c;…...

HarmonyOS4.0系统性深入开发01应用模型的构成要素

应用模型的构成要素 应用模型是HarmonyOS为开发者提供的应用程序所需能力的抽象提炼&#xff0c;它提供了应用程序必备的组件和运行机制。有了应用模型&#xff0c;开发者可以基于一套统一的模型进行应用开发&#xff0c;使应用开发更简单、高效。 HarmonyOS应用模型的构成要…...

线下终端门店调研包含哪些内容

品牌渠道一般分为线上和线下&#xff0c;线上的价格、促销信息、店铺优惠机制等都可以通过登录查看&#xff0c;但是线下门店的数据则需要进店巡查&#xff0c;否则无法得到真实的店铺销售数据&#xff0c;当然也有品牌是靠线下的业务团队报备机制获得这些信息&#xff0c;但是…...

倾斜摄影三维模型数据在行业应用分析

倾斜摄影三维模型数据在行业应用分析 倾斜摄影三维模型数据是一种重要的地理信息资源&#xff0c;可以广泛应用于各个行业和场景&#xff0c;以解决不同领域的问题。以下将详细探讨几个典型的行业或场景&#xff0c;它们利用倾斜摄影三维模型数据解决问题的应用。 1、地理测绘…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...