代码随想录算法训练营第51天 | 139.单词拆分 多重背包理论基础
单词拆分

这道题最后是判断能否组成,很像回溯法的问题形式,和分割回文串那道题比较类似,所以是可以用回溯法解决的,但是回溯法需要使用记忆化递归来避免超时。
class Solution{
public:bool backtracking(const string s, const unordered_set<string>& wordSet, vector<bool>& memory, int startIndex){if(startIndex == s.size()){return true;}// 如果当前位置的memory数组已经更新,直接用memory的结果,不必再一次计算if(!memory[startIndex]) return memory[startIndex];for(int i = startIndex; i < s.size(); i++) {string word = s.substr(startIndex, i - startIndex + 1);if(wordSet.find(word) != wordSet.end() && backtracking(s, wordSet, memory, i + 1)){return true;}}// startIndex位置开始的字符串无法由给定的字符串组成,记录下来memory[startIndex] = false; return false;}bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> memory(s.size(), 1);return backtracking(s, wordSet, memory, 0);}
};
动态规划方法
因为给定的字符串可以重复使用,所以是完全背包。
dp[i]:长度为 i 的字符串,如果可以被拆分成给定的那些字符串,那么dp[i] = true。
递推公式:遍历小于 i 的整数 j,如果dp[j] = true,说明在下标j - 1之前的字符串已经符合要求,同时再满足 [j, i) 的字符串可以在给定数组中找到,那么就可以给 dp[i] 赋值 true。
遍历顺序:匹配字符串是要限制顺序的,所以应该先背包后物品。
class Solution{
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> dp(s.size() + 1, false);dp[0] = true; // 为了递推能够有效地进行for(int i = 1; i <= s.size(); i++) {for(int j = 0; j < i; j++) { // 由于涉及到字符串的索引,同时这里i是长度j是下标,循环结束的判断条件应该自己模拟一下再决定string word = s.substr(j, i - j);if(dp[j] && wordSet.find(word) != wordSet.end()){ // 两项都满足dp[i] = true;}}}return dp[s.size()];}
};
多重背包理论基础

多重背包物品的数目是有限个,我们在遍历的过程中就需要针对某物品考虑到底选几个的问题。方法就是将有多个的物品拆开,这样每一个物品又仅有一个了,多重背包就转化为了01背包。但是这样操作容易超时,可以将遍历物品数目的循环加入到dp数组递推中。
#include <bits/stdc++.h>
using namespace std;
int main() {int bagSize, n;while(cin >> bagSize >> n) {vector<int> weight(n, 0);vector<int> value(n, 0);vector<int> nums(n, 0);for(int i = 0; i < n; i++) cin >> weight[i];for(int i = 0; i < n; i++) cin >> value[i];for(int i = 0; i < n; i++) cin >> nums[i];vector<int> dp(bagSize + 1, 0);for(int i = 0; i < n; i++) {for(int j = bagSize; j >= weight[i]; j--) {for(int k = 1; k <= nums[i] && k * weight[i] <= j; k++) {dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);}}}cout << dp[bagSize] << endl;}
}
相关文章:
代码随想录算法训练营第51天 | 139.单词拆分 多重背包理论基础
单词拆分 这道题最后是判断能否组成,很像回溯法的问题形式,和分割回文串那道题比较类似,所以是可以用回溯法解决的,但是回溯法需要使用记忆化递归来避免超时。 class Solution{ public:bool backtracking(const string s, const …...
weilai8游戏爬虫
#!/usr/bin/python # -*- coding: UTF-8 -*- #!/usr/bin/python # -*- coding: UTF-8 -*- import os,csv import re import random import time import requests from lxml import etreefrom urllib.parse import quote, unquotepage98 sess requests.Session()#创建一个sessi…...
【Java程序设计】【C00261】基于Springboot的休闲娱乐代理售票系统(有论文)
基于Springboot的休闲娱乐代理售票系统(有论文) 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于Springboot的休闲娱乐代理售票系统 本系统分为系统功能模块、管理员功能模块以及用户功能模块。 系统功能模块:休闲娱乐代理…...
【Linux】学习-基础IO拓展篇
Linux基础IO拓展篇—详解文件系统 理解文件系统 在Linux基础IO篇中,我们站在用户的视角对文件进行了理解,主要是针对被打开的文件,那么有没有没有被打开的文件呢?当然有!今天我们换个视角,来站在系统的角…...
算法详解(力扣141——环形链表系列)
博主ID:代码小豪 文章目录 环形链表环形链表的性质分析快慢指针法指针的追及相遇问题 环形链表(2) 环形链表 先来看看环形链表的原题: 中间的部分叙述有点繁杂,简单来概括就是,假如有一个节点,…...
浅谈路由器交换结构
一、路由器技术概述 路由器(Router)是连接两个或多个网络的硬件设备,在网络间起网关的作用,是读取每一个数据包中的地址然后决定如何传送的专用智能性的网络设备。它能够理解不同的协议,例如某个局域网使用的以太网协议…...
Linux第51步_移植ST公司的linux内核第3步_添加修改设备树
1、设备树文件的路径 1)、创建linux中的设备树头文件 在“my_linux/linux-5.4.31/arch/arm/boot/dts/”目录中,以“stm32mp15xx-edx.dtsi”为蓝本,复制一份,并命名为 “stm32mp157d-atk.dtsi”,这就是我们开发板的设备树头文件。…...
【PyTorch】PyTorch中张量(Tensor)统计操作
PyTorch深度学习总结 第五章 PyTorch中张量(Tensor)统计操作 文章目录 PyTorch深度学习总结前言一、最值查找二、特殊值查询 前言 上文介绍了PyTorch中张量(Tensor)的计算操作,本文将介绍张量的统计操作。 一、最值查找 函数描述torch.max()找出张量中的最大值to…...
安卓游戏开发框架应用场景以及优劣分析
一、引言 在移动游戏开发领域,选择合适的开发框架是项目成功的关键因素之一。特别是对于安卓平台,由于其开放性和庞大的用户基础,不同的游戏开发框架应运而生,旨在帮助开发者高效地构建游戏应用。以下是一些流行的安卓游戏开发框架…...
单片机学习笔记---LCD1602
LCD1602介绍 LCD1602(Liquid Crystal Display)液晶显示屏是一种字符型液晶显示模块,可以显示ASCII码的标准字符和其它的一些内置特殊字符(比如日文的片假名),还可以有8个自定义字符 显示容量:…...
django中实现适配器模式
在Django中实现适配器模式(Adapter Pattern)涉及到创建一个适配器类,它允许不兼容的接口之间进行交互。适配器模式通常用于将一个类的接口转换为另一个客户端期望的接口。 一:实现例子 下面是一个简单的例子,演示如何…...
题记(42)--EXCEL排序
目录 一、题目内容 二、输入描述 三、输出描述 四、输入输出示例 五、完整C语言代码 一、题目内容 Excel可以对一组纪录按任意指定列排序。现请你编写程序实现类似功能。 对每个测试用例,首先输出1行“Case i:”,其中 i 是测试用例的编号&#…...
【学网攻】 第(28)节 -- OSPF虚链路
系列文章目录 目录 系列文章目录 文章目录 前言 一、什么是OSPF虚链路? 二、实验 1.引入 实验目标 实验背景 技术原理 实验步骤 实验设备 实验拓扑图 实验配置 扩展 实验拓扑图 实验配置 实验验证 文章目录 【学网攻】 第(1)节 -- 认识网络【学网攻…...
百面嵌入式专栏(面试题)驱动开发面试题汇总1.0
沉淀、分享、成长,让自己和他人都能有所收获!😄 📢本篇我们将介绍驱动开发面试题 。 1、Linux驱动程序的功能是什么? 对设备初始化和释放。进行内核与硬件的数据交互。检测和处理设备出现的错误。2、内核程序中申请内存使用什么函数? 答案:kmalloc()、kzalloc()、vm…...
Starknet 的 JavaScript 库:Starknet.js、get-starknet和starknet-react
文章目录 Starknet 的 JavaScript 库Starknet.jsget-starknetstarknet-reactStarknet 的 JavaScript 库Starknet.js 官方:https://www.starknetjs.com/ Starknet.js 是一个与 Starknet 交互的 JavaScript 库,通常以脚本或去中心化形式进行交互应用程序。 Starknet.js 的灵感…...
debian11 安装 k8s,containerd ,阿里云镜像(已成功)
1. 环境准备 系统要求:至少 2GB RAM(建议 4GB 或更多),网络连接。 节点准备:至少 3 台机器,1 台作为 Master 节点,2 台作为 Worker 节点。 安装sudo apt update apt install sudo设置主机名&a…...
Spring Task定时任务
目录 1、介绍 2、cron表达式 2.1、在线生成器 2.2、通配符 3、代码示例 3.1、使用步骤 3.2、 代码开发 3.3、测试 🍃作者介绍:双非本科大三网络工程专业在读,阿里云专家博主,专注于Java领域学习,擅长web应用开发…...
【设计模式】23中设计模式笔记
设计模式分类 模板方法模式 核心就是设计一个部分抽象类。 这个类具有少量具体的方法,和大量抽象的方法,具体的方法是为外界提供服务的点,具体方法中定义了抽象方法的执行序列 装饰器模式 现在有一个对象A,希望A的a方法被修饰 …...
类加载过程介绍
一、类的生命周期 类被加载到jvm虚拟机内存开始,到卸载出内存为止,他的生命周期可以分为:加载->验证->准备->解析->初始化->使用->卸载。 其中验证、准备、解析统一称为链接阶段 1、加载 将类的字节码载入方法区中…...
pytorch创建模型方式
1.继承自nn.Module的方式 from torch import nn import torch.nn.functional as F 继承自nn.Moduleclass LModel(nn.Module):def __init__(self):super().__init__()self.L1 nn.Linear(10,10)self.L2 nn.Linear(10,64)self.L3 nn.Linear(64,10)self.L4 nn.Linear(10,5)se…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...
