算法分析 KMP算法中next值的计算、0/1背包问题

5.6.1 KMP算法中next值的计算


        设模式的长度为m。用蛮力法求解 KMP算法中的 next值时,next[0]可直接给出,计算next[j](1<=j<=m-1)则需要在 T[0] …T[j-1]中分别取长度为j-1、..、2、1的真前缀和真后缀并比较是否相等,最坏情况下的时间代价是:

但实际上,只需将模式扫描一遍,就能够在线性时间内求得模式的next值。
        因为T[0]既没有真前缀也没有真后缀,因此 next[0]=-1。假设已经计算出next[0],next[1],...,next[j], 如何计算 next[j+1]呢?设 k=next[j], 则 T[0]...T[k-1]=T[j-k]...T[j-1],这意味着 T[0]...T[k-1]是T[0]···T[j-1]的真前缀,同时 T[j-k]...T[j-1]是 T[0]...T[j-1]的真后缀。为了计算 next[j+1],比较 T[k]和T[j],可能出现两种情况:
(1) T[k]=T[j]:说明 T[0]~T[k-1]T[k]=T[j-k]~T[j-1]-T[j], 如图5-15所示。由next值的义,next[j+1]=k+1。

(2) T[k]≠T[j]:此时要找出 T[0]...T[j-1]的真前缀和真后缀相等的第2大子串,由
于T[0]...T[j-1]的真前缀和真后缀相等的最大子串是 T[0]...T[k-1], 而 next[k]的值为T[0].…T[k一1]的真前缀和真后缀相等的最大子串的长度,则 T[0].…T[next[k]-1]即T[0]...T[j-1]的真前缀和真后缀相等的第2大子串,如图5-16所示。令 k=next[k], 再比较T[k]和T[j],此时仍会出现两种情况。当T[k]=T[j]时,与情况(1)类似,此时,next[j+1]=k+1;当T[k]≠T[j]时, 与情况(2)类似,再找出 T[0]...T[k-1]的真前级和真后级相等的最大子串,重复(2)的过程,直至 T[k]=T[j],或 next[k]=-1, 说明T[0]..…T[j-1]不存在真前缀和真后缀相等的子串,此时,next[j+1]=0.

例如,模式 T="abaababc"的next值计算如下。
j=0时,next[0]=-1
j=1时,k=next[0]=-1, next[1]=0
j=2时, k=next[1]=0, T[0]≠T[1];k=next[k]=next[0]=-1.next[2]=0
j=3时,k=next[2]=0, T[0]=T[2]; next[3]=k+1=0+1=1
j=4时, k=next[3]=1, T[1]≠T[3];k=next[k]=next[1]=0, T[0]=T[3], next[4]=k+1=1
j=5时,k=next[4]=1, T[1]=T[4],next[5]=k+1=1+1=2
j=6时,k=next[5]=2, T[2]=T[5],next[6]=k+1=2+1=3
j=7时, k=next[6]=3, T[3]≠T[6];k=next[k]=next[3]=1, T[1]=T[6], next[7]=k+1=2

        基于以上想法,在线性时间内求得模式next值的程序如下。

void GetNext(char T[ ], int next[]){

int j= 0,k=-1;
next[0]=-1;
while (T[j]!='\0') 
{

if (k== -1) {next[++j]= 0;k=0;}
else if (T[j] == T[k])
{

k++;next[++j]= k;

}
else k= next[k];
}
}

5.6.2  0/1 背包问题


【问题】给定几个重量为(w1,w2, .…,wn)、价值为(V1,V2,...,Vn)的物品和一个容量为C的背包,0/1背包问题(0/1 knapsack problem)是求这些物品的一个最有价值的子集,并且要能够装到背包中。


应用实例
有几项可投资的项目,每个项目需要投入资金si,可获利润为Vi,现有可用资金总数为M,应选择哪些项目来投资,可获得最大利润。


【想法】用蛮力法解决0/1背包问题,需要考虑给定n个物品集合的所有子集,找出有总重量不超过背包容量的子集,计算每个可能子集的总价值,然后找到价值最大的子集。例如,给定4个物品的重量为(7,3,4,5),价值为(42, 12,40,25),和一个容量为10的背包,表5-3给出了蛮力法求解0/1背包问题的过程

【算法】 蛮力法求解0/1背包问题的算法用伪代码描述如下。
算法:蛮力法求解 0/1 背包问题
输人:重量(W1, W2, …,Wn),价值(V1, V2,…,Vn),背包容量C
输出:装人背包的物品编号
1. 初始化最大价值 maxValue=0;结果子集S=非空;
2.对集合(1,2, …,n)的每一个子集T,执行下述操作:
2.1 初始化背包的价值value=0;背包的重量 weight=0;
2.2对子集T的每一个元素j执行下述操作:
2.2.1如果 weight+wj < C, 则 weight= weight+ wj, value=value+vj ;
2.2.2 否则,转步骤2考查下一个子集;
2.3 如果 maxValue < value, 则 maxValue=value; S=T;
3.输出子集S中的各元素;
【算法分析】 对于具有n个元素的集合,其子集数量是2^n,所以,无论生成子集的算
法效率有多高,蛮力法求解0/1背包问题的时间下限是Ω(2^n)。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3015753.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

Flume+Hadoop:打造你的大数据处理流水线

引言 在大数据处理中&#xff0c;日志数据的采集是数据分析的第一步。Apache Flume是一个分布式、可靠且可用的系统&#xff0c;用于有效地收集、聚合和移动大量日志数据到集中式数据存储。本文将详细介绍如何使用Flume采集日志数据&#xff0c;并将其上传到Hadoop分布式文件系…

SG-8018CE晶体振荡器可编程规格书

SG-8018CE系列晶体振荡器是一个高性能、多功能且具有高度集成性的解决方案&#xff0c;它满足了现代电子系统的严格要求。其广泛的频率范围0.67 MHz到170 MHz&#xff0c;且频率调节精度达到1ppm&#xff0c;1.62 V至3.63V的宽广电源电压&#xff0c;使能&#xff08;OE&#x…

Codigger:Web应用赋能的分布式操作系统让用户卓越体验

Codigger&#xff0c;作为一个分布式操作系统&#xff0c;其独特之处在于其采用的浏览器/服务器&#xff08;Browser/Server&#xff0c;简称B/S&#xff09;架构。这种架构的核心思想是&#xff0c;通过浏览器来进入工作界面&#xff0c;页面交互部分事务逻辑在前端&#xff0…

2024------MySQL数据库基础知识点总结

-- 最好的选择不是最明智的&#xff0c;而是最勇敢的&#xff0c;最能体现我们真实意愿的选择。 MySQL数据库基础知识点总结 一、概念 数据库&#xff1a;DataBase&#xff0c;简称DB。按照一定格式存储数据的一些文件的组合顾名思义: 存储数据的仓库&#xff0c;实际上就是一…

汉王科技亮相世界数字健康论坛:以AI定义第四代血压计

作为科技行业的年度盛会&#xff0c;2024年中关村论坛年会于近日在北京揭幕。 作为中关村知名的人工智能企业&#xff0c;汉王科技携大模型的最新垂直应用、柯氏音法电子血压计等创新成果&#xff0c;在4月29日中关村论坛平行论坛“2024世界数字健康论坛”上亮相。 在《AI赋能血…

PE文件(四)FileBuffer-ImageBuffer作业

C语言实现如下功能 2.编写一个函数&#xff0c;将RVA的值转换成FOA 将文件加载到内存时&#xff0c;已知一个数据在内存中的地址&#xff0c;将此地址转化成文件在硬盘上时的相对于文件起始地址的文件偏移地址。即将虚拟内存偏移地址转换成文件偏移地址。 说明&#xff1a;这里…

安装nvm切换多个nodejs

今天实习&#xff0c;用到了公司的老项目vue2的&#xff0c;需要更换nodejs版本 我想直接安装一个16版本的&#xff0c;然后自己在webstrom中配置一下exe文件就可以了。 然而第一步就不行&#xff0c;在安装另一版本中显示 然后博主在这里介绍一下怎么使用nvm可以快速切换node…

ROS机械臂中Movelt!

Movelt!简介 一个易于集成使用的集成化开发平台 由一系列移动操作的功能包组成 1、运动规划 2、操作控制 3、3D感知 4、运动学 5、控制与导航算法 ....... 提供友好的GUI 可应用于工业、商业、研发和其他领域 ROS社区中使用度排名前三的功能包 Movelt!三大核心功能 …

成功案例(IF=7.3)| 转录组+蛋白质组+代谢组联合分析分析揭示胰腺癌中TAM2相关的糖酵解和丙酮酸代谢重构

研究背景 肿瘤的进展和发展需要癌细胞的代谢重编程&#xff0c;癌细胞能量代谢模式的改变可以满足快速增殖和适应肿瘤微环境的需要。肿瘤微环境&#xff08;TME&#xff09;中的代谢状态受到多种因素的影响&#xff0c;包括血管生成、与其他细胞的相互作用和系统代谢。代谢异质…

临时邮箱API发送邮件的安全性?如何保障?

临时邮箱API发送邮件的步骤有哪些&#xff1f;设置邮箱API方法&#xff1f; 电子邮件作为一种重要的通信方式&#xff0c;而临时邮箱API作为一种新兴的邮件发送技术&#xff0c;其安全性更是成为大家关注的焦点。那么&#xff0c;临时邮箱API发送邮件的安全性究竟如何呢&#…

doris经典bug

在部署完登录web页面查看的时候会发现只有一个节点可以读取信息剩余的节点什么也没读取到 在发现问题后&#xff0c;我们去对应的节点去看log日志&#xff0c;发现它自己绑定到前端的地址上了 现在我们已经发现问题了&#xff0c;以下就开始解决问题 重置doris 首先对be进行操…

IIoT:数据融合在工业物联网中的应用——青创智通

工业物联网解决方案-工业IOT-青创智通 随着科技的不断发展&#xff0c;工业物联网&#xff08;IIoT&#xff09;已经逐渐渗透到各个行业&#xff0c;为企业的生产和管理带来了前所未有的便利。 然而&#xff0c;与此同时&#xff0c;海量的数据也为企业带来了挑战。如何将这些…

宜选影票在线选座电影票小程序开发如何获取api接口?

要开发一个在线选座电影票小程序并获取API接口&#xff0c;你需要遵循几个关键步骤。以下是通常的流程&#xff1a; 明确需求和目标&#xff1a; 在开始之前&#xff0c;明确你的小程序需要哪些功能&#xff0c;例如电影查询、场次查询、在线选座、购票支付等。确定你需要从AP…

07_Flutter使用NestedScrollView+TabBarView滚动位置共享问题修复

07_Flutter使用NestedScrollViewTabBarView滚动位置共享问题修复 一.案发现场 可以看到&#xff0c;上图中三个列表的滑动位置共享了&#xff0c;滑动其中一个列表&#xff0c;会影响到另外两个&#xff0c;这显然不符合要求&#xff0c;先来看下布局&#xff0c;再说明产生这个…

5.7代码

1.环境治理 分析&#xff1a;最开始进入了一个误区&#xff0c;觉得都有通路了直接算通路就可以&#xff0c;后来才发现居然是最小路径的总和&#xff0c;所以大概是每减一次都要算一次各点之间的最小路径了&#xff0c;然后是循环&#xff0c;到需要的条件为止 总的来说思路不…

VMware 替代专题|14 个常见问题,解读 VMware 替代的方方面面

随着 VMware by Broadcom 调整订阅模式和产品组合&#xff0c;不少用户也将 VMware 替代提上日程。为了帮助用户顺利完成从 VMware 替代方案评估到产品落地的一系列环节&#xff0c;我们通过这篇博客&#xff0c;对 VMware 替代场景下用户经常遇到的问题进行了梳理和解答。 更…

绘画作品3d数字云展厅提升大众的艺术鉴赏和欣赏能力

3D虚拟展厅作为未来艺术的展示途径&#xff0c;正逐渐成为文化创意产业蓬勃发展的重要引擎。这一创新形式不仅打破了传统艺术展览的局限性&#xff0c;更以其独特的魅力吸引着全球观众的目光。 3D虚拟艺术品展厅以其独特的魅力&#xff0c;助力提升大众的艺术鉴赏和欣赏能力。观…

redis 使用记录

redis 使用记录 下载运行配置文件启动 参考 下载 github: Redis for Windows 或者从百度网盘下载 Redis version 3.2.100 链接: https://pan.baidu.com/s/1kxNOuZFunvVhVy1cfQzCDA?pwdpibh 运行 双击运行 运行效果 如果出错&#xff1a;查看是否项目路径是否包含中文 配…

1688工厂货源API接口:用于商品采集、商品搜索、商品详情数据抓取

item_get 获得1688商品详情item_search 按关键字搜索商品item_search_img 按图搜索1688商品&#xff08;拍立淘&#xff09;item_search_suggest 获得搜索词推荐item_fee 获得商品快递费用seller_info 获得店铺详情item_search_shop 获得店铺的所有商品item_password 获得淘口令…

端侧AI从“芯”开发机会到来,MediaTek举办天玑开发者大会MDDC2024

MDDC2024速览&#xff1a; 发布芯片新品MediaTek天玑9300旗舰5G生成式AI移动芯片、生态发布天玑AI先锋计划、for开发者的生成式AI端侧“天玑AI开发套件”、发布《生成式AI手机产业白皮书》、for游戏的MediaTek星速引擎技术…… MediaTek 5月27日举办天玑开发者大会2024&#xf…