代码随想录算法训练营第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…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...
