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

Day40- 动态规划part08

一、单词拆分

题目一:139. 单词拆分

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true

注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

定义一个布尔型的动态规划数组dp

dp[i]表示字符串s的前i个字符能否被字典wordDict中的一个或多个单词拼接出来

dp[0]为真,因为空字符串总是可以被拼接出来的

对于字符串s中的每一个位置i(从1到字符串长度),遍历i之前的所有位置j(从0到i-1),检查从ji的子字符串是否存在于字典wordDict

/** @lc app=leetcode.cn id=139 lang=cpp** [139] 单词拆分*/// @lc code=start
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> dict(wordDict.begin(), wordDict.end());vector<bool> dp(s.length() + 1, false);dp[0] = true; // 空字符串总是可以被拼接for (int i = 1; i <= s.length(); ++i) {for (int j = 0; j < i; ++j) {if (dp[j] && dict.find(s.substr(j, i - j)) != dict.end()) {dp[i] = true;break; // 找到一种拼接方式即可}}}return dp[s.length()];}
};
// @lc code=end

二、多重背包

56. 携带矿石资源(第八期模拟笔试)

时间限制:5.000S  空间限制:256MB

题目描述

你是一名宇航员,即将前往一个遥远的行星。在这个行星上,有许多不同类型的矿石资源,每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球,但你的宇航舱有一定的容量限制。 

给定一个宇航舱,最大容量为 C。现在有 N 种不同类型的矿石,每种矿石有一个重量 w[i],一个价值 v[i],以及最多 k[i] 个可用。不同类型的矿石在地球上的市场价值不同。你需要计算如何在不超过宇航舱容量的情况下,最大化你所能获取的总价值。

输入描述

输入共包括四行,第一行包含两个整数 C 和 N,分别表示宇航舱的容量和矿石的种类数量。 

接下来的三行,每行包含 N 个正整数。具体如下: 

第二行包含 N 个整数,表示 N 种矿石的重量。 

第三行包含 N 个整数,表示 N 种矿石的价格。 

第四行包含 N 个整数,表示 N 种矿石的可用数量上限。

输出描述

输出一个整数,代表获取的最大价值。

动态规划数组dp[j]表示容量为j的背包所能装下的最大价值。对于每种矿石i,遍历背包容量j从大到小,更新dp[j]

具体实现步骤如下:

  1. 对于每种矿石i,将其按数量k[i]进行二进制拆分,比如如果k[i] = 4,可以拆分为1,2,1(共计4个),这样就将问题转化为了多个0-1背包问题。
  2. 对于每个拆分后的矿石,更新dp[j]
#include <iostream>
#include <vector>
using namespace std;int main() {int C, N;cin >> C >> N;vector<int> w(N), v(N), k(N);for (int i = 0; i < N; ++i) cin >> w[i];for (int i = 0; i < N; ++i) cin >> v[i];for (int i = 0; i < N; ++i) cin >> k[i];vector<int> dp(C + 1, 0);for (int i = 0; i < N; ++i) {int num = k[i];for (int k = 1; num > 0; k *= 2) { int mul = min(k, num);int weight = w[i] * mul;int value = v[i] * mul;for (int j = C; j >= weight; --j) {dp[j] = max(dp[j], dp[j - weight] + value);}num -= mul;}}cout << dp[C] << endl;return 0;
}

相关文章:

Day40- 动态规划part08

一、单词拆分 题目一&#xff1a;139. 单词拆分 139. 单词拆分 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意&#xff1a;不要求字典中出现的单词全部都使用&#xff0c;并且字典中的单词可以…...

论文笔记:相似感知的多模态假新闻检测

整理了RecSys2020 Progressive Layered Extraction : A Novel Multi-Task Learning Model for Personalized Recommendations&#xff09;论文的阅读笔记 背景模型实验 论文地址&#xff1a;SAFE 背景 在此之前&#xff0c;对利用新闻文章中文本信息和视觉信息之间的关系(相似…...

5G技术对物联网的影响

随着数字化转型的加速&#xff0c;5G技术作为通信领域的一次重大革新&#xff0c;正在对物联网&#xff08;IoT&#xff09;产生深远的影响。对于刚入行的朋友们来说&#xff0c;理解5G技术及其对物联网应用的意义&#xff0c;是把握行业发展趋势的关键。 让我们简单了解什么是…...

Nacos1.X源码解读(待完善)

目录 下载源码 注册服务 客户端注册流程 注册接口API 服务端处理注册请求 设计亮点 服务端流程图 下载源码 1. 克隆git地址到本地 # 下载nacos源码 git clone https://github.com/alibaba/nacos.git 2. 切换分支到1.4.7, maven编译(3.5.1) 3. 找到启动类com.alibaba.na…...

算法之双指针系列1

目录 一&#xff1a;双指针的介绍 1&#xff1a;快慢指针 2&#xff1a;对撞指针 二&#xff1a;对撞指针例题讲述 一&#xff1a;双指针的介绍 在做题中常用两种指针&#xff0c;分别为对撞指针与快慢指针。 1&#xff1a;快慢指针 简称为龟兔赛跑算法&#xff0c;它的基…...

苍穹外卖面试题

8. 如何理解分组校验 很多情况下&#xff0c;我们会将校验规则写到实体类中的属性上&#xff0c;而这个实体类有可能作为不同功能方法的参数使用&#xff0c;而不同的功能对象参数对象中属性的要求是不一样的。比如我们在新增和修改一个用户对象时&#xff0c;都会接收User对象…...

【Qt 学习之路】在 Qt 使用 ZeroMQ

文章目录 1、概述2、ZeroMQ介绍2.1、ZeroMQ 是什么2.2、ZeroMQ 主线程与I/O线程2.3、ZeroMQ 4种模型2.4、ZeroMQ 相关地址 3、Qt 使用 ZeroMQ3.1、下载 ZeroMQ3.2、添加 ZeroMQ 库3.3、使用 ZeroMQ3.4、相关 ZeroMQ 案例 1、概述 今天是大年初一&#xff0c;先给大家拜个年&am…...

CI/CD到底是啥?持续集成/持续部署概念解释

前言 大家好&#xff0c;我是chowley&#xff0c;日常工作中&#xff0c;我每天都在接触CI/CD&#xff0c;今天就给出我心中的答案。 在现代软件开发中&#xff0c;持续集成&#xff08;Continuous Integration&#xff0c;CI&#xff09;和持续部署&#xff08;Continuous D…...

golang常用库之-disintegration/imaging图片操作(生成缩略图)

文章目录 golang常用库之什么是imaging库导入和使用生成缩略图 golang常用库之 什么是imaging库 官网&#xff1a;https://github.com/disintegration/imaging imaging 是一个 Go 语言的图像处理库&#xff0c;它提供了一组功能丰富的函数和方法&#xff0c;用于进行各种图像…...

CSS 控制 video 标签的控制栏组件的显隐

隐藏下载功能 <video src"" controlsList"nodownload" />controlslist 取值如下(设定多个值则使用空格进行间隔) 如&#xff1a;controlslist"nodownload nofullscreen noremoteplayback"nodownload&#xff1a;取消更多控件弹窗的下载功…...

数据可视化之维恩图 Venn diagram

文章目录 一、前言二、主要内容三、总结 &#x1f349; CSDN 叶庭云&#xff1a;https://yetingyun.blog.csdn.net/ 一、前言 维恩图&#xff08;Venn diagram&#xff09;&#xff0c;也叫文氏图或韦恩图&#xff0c;是一种关系型图表&#xff0c;用于显示元素集合之间的重叠区…...

2024刘谦春晚第二个扑克牌魔术

前言 就是刚才看春晚感觉这个很神奇&#xff0c;虽然第一个咱模仿不过来&#xff0c;第二个全国人民这么多人&#xff0c;包括全场观众都有成功&#xff0c;这肯定是不需要什么技术&#xff0c;那我觉得这个肯定就是数学了&#xff0c;于是我就胡乱分析一通。 正文 首先准备…...

【k8s系列】(202402) 证书apiserver_client_certificate_expiration_seconds

apiserver_client_certificate_expiration_second证书定义的位置&#xff1a;kubernetes/staging/src/k8s.io/apiserver/pkg/authentication/request/x509/x509.go at 244fbf94fd736e94071a77a8b7c91d81163249d4 kubernetes/kubernetes (github.com) apiserver_client_certi…...

Rust变量与常量介绍

Rust是一门注重安全性和性能的系统编程语言&#xff0c;其中变量和常量的概念有着独特的设计和特性。在本文中&#xff0c;我们将深入了解Rust中的变量和常量&#xff0c;并解释它们之间的区别&#xff0c;同时通过多个例子进行说明。 Rust常量 在Rust中&#xff0c;常量是不…...

Flask基础学习2

连接mysql数据库测试(专业版) [注意1&#xff1a;要导入text库&#xff0c;否则可能出现找不到select 1错误] [注意2&#xff1a;若出现下列问题&#xff0c;可按照模板代码的顺序db SQLAlchemy(app) 的位置] RuntimeError: Either SQLALCHEMY_DATABASE_URI or SQLALCHEMY_B…...

文章页的上下篇功能是否有必要?boke112百科取消上下篇功能

也不知道是从什么时候开始&#xff0c;我们很多站长的博客网站文章页都会在文末添加上“上一篇”和“下一篇”功能&#xff0c;目的是进行站内SEO优化和方便用户阅读上下篇文章。 boke112百科不管是以前使用的Three主题还是现在使用的YIA主题&#xff0c;刚开始的文章页都是有…...

Lua序列化

我们经常需要序列化一些数据&#xff0c;为了将数据转换为字节流或者字符流&#xff0c;这样我们就可以保存到文件或者通过网络发送出去。我们可以在 Lua 代码中描述序列化的数据&#xff0c;在这种方式下&#xff0c;我们运行读取程序即可从代码中构造出保存的值。 number/st…...

Acwing---839. 模拟堆

模拟堆 1.题目2.基本思想3.代码实现 1.题目 维护一个集合&#xff0c;初始时集合为空&#xff0c;支持如下几种操作&#xff1a; I x&#xff0c;插入一个数 x&#xff1b;PM&#xff0c;输出当前集合中的最小值&#xff1b;DM&#xff0c;删除当前集合中的最小值&#xff08…...

STM32 STD/HAL库驱动W25Q64模块读写字库数据+OLED0.96显示例程

STM32 STD/HAL库驱动W25Q64 模块读写字库数据OLED0.96显示例程 &#x1f3ac;原创作者对W25Q64保存汉字字库演示&#xff1a; W25Q64保存汉字字库 &#x1f39e;测试字体显示效果&#xff1a; &#x1f4d1;功能实现说明 利用W25Q64保存汉字字库&#xff0c;OLED显示汉字的时…...

Android 移动应用开发 创建第一个Android项目

文章目录 一、创建第一个Android项目1.1 准备好Android Studio1.2 运行程序1.3 程序结构是什么app下的结构res - 子目录&#xff08;所有图片、布局、字AndroidManifest.xml 有四大组件&#xff0c;程序添加权限声明 Project下的结构 二、开发android时&#xff0c;部分库下载异…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

(二)原型模式

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

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

数据结构:泰勒展开式:霍纳法则(Horner‘s Rule)

目录 &#x1f50d; 若用递归计算每一项&#xff0c;会发生什么&#xff1f; Horners Rule&#xff08;霍纳法则&#xff09; 第一步&#xff1a;我们从最原始的泰勒公式出发 第二步&#xff1a;从形式上重新观察展开式 &#x1f31f; 第三步&#xff1a;引出霍纳法则&…...

C++ 类基础:封装、继承、多态与多线程模板实现

前言 C 是一门强大的面向对象编程语言&#xff0c;而类&#xff08;Class&#xff09;作为其核心特性之一&#xff0c;是理解和使用 C 的关键。本文将深入探讨 C 类的基本特性&#xff0c;包括封装、继承和多态&#xff0c;同时讨论类中的权限控制&#xff0c;并展示如何使用类…...

运行vue项目报错 errors and 0 warnings potentially fixable with the `--fix` option.

报错 找到package.json文件 找到这个修改成 "lint": "eslint --fix --ext .js,.vue src" 为elsint有配置结尾换行符&#xff0c;最后运行&#xff1a;npm run lint --fix...

20250609在荣品的PRO-RK3566开发板的Android13下解决串口可以执行命令但是脚本执行命令异常的问题

20250609在荣品的PRO-RK3566开发板的Android13下解决串口可以执行命令但是脚本执行命令异常的问题 2025/6/9 20:54 缘起&#xff0c;为了跨网段推流&#xff0c;千辛万苦配置好了网络参数。 但是命令iptables -t filter -F tetherctrl_FORWARD可以在调试串口/DEBUG口正确执行。…...

2025-06-08-深度学习网络介绍(语义分割,实例分割,目标检测)

深度学习网络介绍(语义分割,实例分割,目标检测) 前言 在开始这篇文章之前&#xff0c;我们得首先弄明白&#xff0c;什么是图像分割&#xff1f; 我们知道一个图像只不过是许多像素的集合。图像分割分类是对图像中属于特定类别的像素进行分类的过程&#xff0c;即像素级别的…...

时间序列预测的机器学习方法:从基础到实战

时间序列预测是机器学习中一个重要且实用的领域&#xff0c;广泛应用于金融、气象、销售预测、资源规划等多个行业。本文将全面介绍时间序列预测的基本概念、常用方法&#xff0c;并通过Python代码示例展示如何构建和评估时间序列预测模型。 1. 时间序列预测概述 时间序列是按…...

ubuntu 20.04挂载固态硬盘

我们有个工控机&#xff0c;其操作系统是ubuntu 20.04。可以接入一个固态硬盘。将固态硬盘插好后&#xff0c;就要进行挂载。在AI的指导下&#xff0c;过程并不顺利。记录如下&#xff1a; 1、检查硬盘是否被识别 安装好硬盘后&#xff0c;运行以下命令来检查Linux系统是否…...