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

代码随想录算法训练营第46天|139.单词拆分、多重背包问题

139.单词拆分

题目链接:单词拆分

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

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

解题思路:

动规五部曲分析如下:

  1. 确定dp数组以及下标的含义
    dp[i]:表示字符串 s前i个字符组成的字符串 s[0…i−1]是否能被拆分成若干个字典中出现的单词

  2. 确定递推公式
    每次转移的时候我们需要枚举包含位置i-1的最后一个单词,看它是否出现在字典中以及除去这部分的字符串是否合法即可。使用变量j遍历分割长度为i的字符串,如果字符串[0……j-1]能被字典中的单词拆分并且字符串[j……i-1]在字典中则dp[i]为true。

    dp[i]=dp[j] && check(s[ji−1])

  3. dp数组如何初始化
    dp[0]=true 表示空串且合法。

  4. 确定遍历顺序
    先遍历字符串i,再遍历子串在字符串中的终止位置j。

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> dict(wordDict.begin(), wordDict.end());vector<bool> dp(s.size() + 1, false);dp[0] = true;for (int j = 0; j <= s.size(); j++) {for (int i = 0; i < j; i++) {string str = s.substr(i, j - i);if (dict.find(str) != dict.end() && dp[i] == true)dp[j] = true;}}return dp[s.size()];}
};

多重背包问题

题目描述:有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用,每件耗费的空间是Ci ,价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量,且价值总和最大。

解题思想:

多重背包和01背包是非常像的, 为什么和01背包像呢?

每件物品最多有Mi件可用,把Mi件摊开,其实就是一个01背包问题了。

例如:背包最大重量为10。

物品为:

重量价值数量
物品01152
物品13203
物品24302

问背包能背的物品最大价值是多少?

和如下情况有区别么?

重量价值数量
物品01151
物品01151
物品13201
物品13201
物品13201
物品24301
物品24301

毫无区别,这就转成了一个01背包问题了,且每个物品只用一次。

#include <iostream>
#include <vector>using namespace std;
int main(int argc, char *argv[]) {int bagWeight, n;cin >> bagWeight>>n;vector<int> weights(n),values(n),nums(n);int x;for (int i = 0; i < n; i++) cin>>weights[i];for (int i = 0; i < n; i++) cin>>values[i];	for (int i = 0; i < n; i++) cin>>nums[i];for (int i = 0; i < n; i++){int num = nums[i];num--;while(num--){weights.push_back(weights[i]);values.push_back(values[i]);}}vector<int> dp(bagWeight+1,0);for (int i = 0; i < weights.size(); i++){for (int j = bagWeight; j>=weights[i];j--){dp[j] = max(dp[j],dp[j-weights[i]]+values[i]);}}cout << dp[bagWeight];}

这里也有另一种实现方式,就是把每种商品遍历的个数放在01背包里面在遍历一遍。

#include <iostream>
#include <vector>using namespace std;
int main(int argc, char *argv[]) {int bagWeight, n;cin >> bagWeight>>n;vector<int> weights(n),values(n),nums(n);int x;for (int i = 0; i < n; i++) cin>>weights[i];for (int i = 0; i < n; i++) cin>>values[i];	for (int i = 0; i < n; i++) cin>>nums[i];vector<int> dp(bagWeight+1,0);for (int i = 0; i < weights.size(); i++){for (int j = bagWeight; j>=weights[i];j--){for (int k = 1; k <= nums[i] && (j - k * weights[i]) >= 0; k++)dp[j] = max(dp[j],dp[j-weights[i]*k]+values[i]*k);}}cout << dp[bagWeight];return 0;
}

相关文章:

代码随想录算法训练营第46天|139.单词拆分、多重背包问题

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

数组与伪数组的区别

大家都知道&#xff0c;在js中使用 document.querySelectorAll(选择器&#xff09;获取到的为该选择器能选择到的所有元素组成的伪数组&#xff0c;所谓伪数组&#xff0c;就是外表和数组一样&#xff0c;能够使用索引遍历&#xff0c;但本质是对象。 数组与伪数组之间的区别&…...

Java集合List

List特有方法 经典多态写法 // 经典的多态写法 List<String> list new ArrayList<>();常用API&#xff1a;增删改查 // 添加元素 list.add("Java"); // 添加元素到指定位置 list.add(0, "Python");// 获取元素 String s list.get(0);// 修改…...

elasticsearch基础命令

1 字段分词分析: GET /store_info_data/_analyze {"field": "storeName","text":"20pilapala0" }2 精确查找,去除评分 GET /store_info_data/_search {"query": {"constant_score": {"filter": {&quo…...

Capture One 23 Enterprise for Mac中文版 全面的图像处理工具

Capture One 23 Enterprise for Mac中文版一款专业的图像编辑和管理软件&#xff0c;具备强大的功能和工具&#xff0c;适用于摄影师、摄影工作室和专业用户。 软件下载&#xff1a;Capture One 23 Enterprise for Mac中文版下载 该软件为用户提供了全面的图像处理工具&#xf…...

Qt案例 通过调用Setupapi.h库实现对设备管理器中设备默认驱动的备份

参考腾讯电脑管家-软件市场中的驱动备份专家写的一个驱动备份软件案例&#xff0c;学习Setupapi.h库中的函数使用.通过Setupapi.h库读取设备管理器中安装的设备获取安装的驱动列表&#xff0c;通过bit7z库备份驱动目录下的所有文件. 目录导读 实现效果相关内容示例获取SP_DRVIN…...

如何理解JVM

JVM&#xff08;Java虚拟机&#xff09;是Java程序的运行环境&#xff0c;它是Java技术的核心组成部分之一。理解JVM涉及到以下几个方面的内容&#xff1a; 1. **虚拟机概念**&#xff1a;虚拟机是一种软件实体&#xff0c;它在物理计算机上模拟出一个计算机系统&#xff0c;使…...

第十四讲:C语言字符函数和字符串函数

目录 1. 字符分类函数 2、字符转换函数 3. strlen的使⽤和模拟实现 4. strcpy 的使⽤和模拟实现 5. strcat 的使⽤和模拟实现 6. strcmp 的使⽤和模拟实现 7. strncpy 函数的使⽤ 8. strncat 函数的使⽤ 9. strncmp函数的使⽤ 10. strstr 的使⽤和模拟实现 11. strt…...

华为海思2024春招数字芯片岗机试题(共9套)

huawei海思2024春招数字芯片岗机试题(共9套&#xff0c;有答案和解析&#xff0c;答案非官方&#xff0c;未仔细校正&#xff0c;仅供参考&#xff09;&#xff08;WX:didadidadidida313&#xff0c;加我备注&#xff1a;CSDN huawei数字题目&#xff0c;谢绝白嫖哈&#xff09…...

分类预测 | Matlab实现KPCA-IDBO-LSSVM基于核主成分分析和改进蜣螂优化算法优化最小二乘支持向量机分类预测

分类预测 | Matlab实现KPCA-IDBO-LSSVM基于核主成分分析和改进蜣螂优化算法优化最小二乘支持向量机分类预测 目录 分类预测 | Matlab实现KPCA-IDBO-LSSVM基于核主成分分析和改进蜣螂优化算法优化最小二乘支持向量机分类预测分类效果基本描述程序设计参考资料 分类效果 基本描述…...

与机器对话:ChatGPT 和 AI 语言模型的奇妙故事

原文&#xff1a;Talking to Machines: The Fascinating Story of ChatGPT and AI Language Models 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 从 ELIZA 到 ChatGPT&#xff1a;会话式人工智能的简史 会话式人工智能是人工智能&#xff08;AI&#xff09;的一个分…...

概率论基础——拉格朗日乘数法

概率论基础——拉格朗日乘数法 概率论是机器学习和优化领域的重要基础之一&#xff0c;而拉格朗日乘数法与KKT条件是解决优化问题中约束条件的重要工具。本文将简单介绍拉格朗日乘数法的基本概念、应用以及如何用Python实现算法。 1. 基本概念 拉格朗日乘数法是一种用来求解…...

[xboard]real6410-6.2 移植kernel网络驱动

文章目录 硬件电路软件配置问题1问题2问题3问题4功能测试硬件电路 核心板,使用DM9000A [图片] 软件配置 问题1 / # / # ifconfig ifconfig: /proc/net/dev: No such file or directory ifconfig: socket: Fun...

Quarkus初探

Quarkus初探 背景安装Quarkus安装Quarkus CLI 创建Quarkus项目运行Quarkus初探代码修改一下代码 数据持久化创建PanacheEntiry写入数据读取数据 Dev Service使用外部数据库区分dev和prod 构建native应用&#xff08;依赖Graalvm&#xff09; 背景 最早是在Infoq上了解到Quarku…...

90天玩转Python-02-基础知识篇:初识Python与PyCharm

90天玩转Python系列文章目录 90天玩转Python—01—基础知识篇&#xff1a;C站最全Python标准库总结 90天玩转Python--02--基础知识篇&#xff1a;初识Python与PyCharm 90天玩转Python—03—基础知识篇&#xff1a;Python和PyCharm&#xff08;语言特点、学习方法、工具安装&…...

List操作的一些常见问题

1. Arrays.asList转换基本类型数组 在实际的业务开发中&#xff0c;我们通常会进行数组转List的操作&#xff0c;通常我们会使用Arrays.asList来进行转换&#xff0c;但是在转换基本类型的数组的时候&#xff0c;却出现转换的结果和我们想象的不一致。 import java.util.Arra…...

如何使用Java和RabbitMQ实现延迟队列?

前言 今天我们使用Java和RabbitMQ实现消息队列的延迟功能。 前期准备&#xff0c;需要安装好docker、docker-compose的运行环境。 需要安装RabbitMQ的可以看下面这篇文章。 如何使用PHP和RabbitMQ实现消息队列&#xff1f;-CSDN博客 今天讲的是依赖RabbitMQ的延迟插件实现…...

AI论文速读 | TF-LLM:基于大语言模型可解释性的交通预测

论文标题&#xff1a; Explainable Traffic Flow Prediction with Large Language Models 作者&#xff1a;Xusen Guo, Qiming Zhang, Mingxing Peng, Meixin Zhu(朱美新)*, Hao (Frank)Yang(杨昊) 机构&#xff1a;香港科技大学&#xff08;广州&#xff09;&#xff0c;约翰…...

智慧矿山视频智能监控与安全监管方案

一、行业背景 随着全球能源需求的日益增长&#xff0c;矿业行业作为国民经济的重要支柱&#xff0c;其发展日益受到广泛关注。然而&#xff0c;传统矿山管理模式的局限性逐渐显现&#xff0c;如生产安全、人员监管、风险预警等方面的问题日益突出。因此&#xff0c;智慧矿山智…...

2024春算法训练4——函数与递归题解

一、前言 感觉这次的题目都很好&#xff0c;但是E题....&#xff08;我太菜了想不到&#xff09;&#xff0c;别人的题解都上百行了&#xff0c;晕&#xff1b; 二、题解 A-[NOIP2010]数字统计_2024春算法训练4——函数与递归 (nowcoder.com) 这种题目有两种做法&#xff1a;…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...