算法快学笔记（十六）：动态规划

2024-02-14 11:08
文章标签 算法 动态 规划 笔记 十六 快学

本文主要是介绍算法快学笔记（十六）：动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 介绍

前文提到，对于背包问题与旅行商问题，计算的复杂度是随着计算数据的增加呈现指数级增长的，贪婪算法算可以处理，但得到的并不是最优解。

动态规划的主要思路是先解决子问题，在逐步解决大问题。本文将通过两个例子介绍动态规划的推算思路。

2. 背包问题

2.1 思路

通过动态规划方法解决背包问题的流程如下：

  1. 准备一个表格，商品作为Y轴，背包重量作为x轴

  2. 使用下面的公式算出价格且更新到表格里
    在这里插入图片描述

  3. 使用方法2，逐行填充表格，直到将表格填满。

2.2 推算过程

用于推算的数据如下：

  1. 小偷的背包可以放4KG的物品
  2. 可偷物品的价格，重量如下：
物品重量价值
吉他1kg1500
音响4kg3000
笔记本3kg2000
手机1kg2000

详细推算过程如下:

  1. 初始化表格如下
*1234
吉他
音响
笔记本
手机
  1. 吉他是第一个商品，且重量只有1kg,则对于不同大小的背包而言都可以放得下，所以第一行的值都为1500
*1234
吉他1500150015001500
音响
笔记本
手机
  1. 音响是第二个商品，对于1,2,3三个背包都放不下，所以能放的物品价值还是1500,第四个背包可以放下，使前面提到的公式推导一下。
  • CELL[1][4]=1500
  • 当前价值+剩余空间价值=3000+0(没有剩余的空间，所以剩余价值为0)
    通过上面的推算，可知音响这行最后一格的值为3000
*1234
吉他1500150015001500
音响1500150015003000
笔记本
手机
  1. 看下笔记本，前两个背包都放不下，从第三个开始。第三个背包放完笔记本后价值为2000,且比CELL[2,3]要大，所以该值更新为2000
*1234
吉他1500150015001500
音响1500150015003000
笔记本150015002000
手机

再来看笔记本的最后一格,比较下面的值：

  • CELL[2][4]=3000
  • 2000(笔记本价格)+1500(剩余空间的最大价值)=3500

由上可得出笔记本第四格的价值应该是3500

*1234
吉他1500150015001500
音响1500150015003000
笔记本1500150020003500
手机
  1. 手机的重量为1kg.且比吉他的价格要贵，所以第一格替换成手机的价格
*1234
吉他1500150015001500
音响1500150015003000
笔记本1500150020003500
手机2000

对于第二格，比较下面的值：

  • CELL[3][2]=1500
  • 2000(笔记本价格)+1500(剩余空间的最大价值，C[3,1])=3500

由上可得出手机第二格的价值应该是3500

*1234
吉他1500150015001500
音响1500150015003000
笔记本1500150020003500
手机20003500

第三格的推算过程与第二格类似，值同样为3500.

*1234
吉他1500150015001500
音响1500150015003000
笔记本1500150020003500
手机200035003500

对于第四格，比较下面的值：

  • CELL[3][4]=3500
  • 2000(笔记本价格)+2000(剩余空间的最大价值，C[3,3])=4000

由上可得出手机第四格的价值应该是4000

*1234
吉他1500150015001500
音响1500150015003000
笔记本1500150020003500
手机2000350035004000

最终可得知，小偷最多可偷4000元的商品，且偷的商品是手机+笔记本电脑。

2.4 其他注意事项

  1. 最终的结果和表格中商品的顺序没有关系
  2. 如果可偷的商品为0.5kg. 则x轴的粒度要为0.5。既0.5->1->1.5->2…
  3. 选择商品的时候，每个商品都是独立选择的，不存在依赖关系。例如不应该出现选择商品A，则必须（不能）选择B的情况
  4. 最优解可能会导致最终的背包没有被装满

3. 最长公共子串

最场公共子串求出的是两个字符串都包含的最长子串，例如:对于hish与fish两个单词，ish就是他们的最长公共子串。

3.1 思路

可以用解决背包问题的思路来解决该问题，两个单词分别对应纵/横轴，将公共子串的长度填到方格里，最后所有格子里最大的值就是最大的公共子串的长度，连续从0到最大长度值对应的纵/横轴对应的字母就是最长公共子串。

格子里值的推算公式如下：

if word_a[i] == word_b[j]:cell[i][j] = cell[i-1][j-1] + 1
else:cell[i][j] = 0

在这里插入图片描述

按照上面的公式推算，FISH与HISH的结果如下：

在这里插入图片描述

既最大长度为3,对应的子串为ISH.

3.2 最长公共子序列

最长公共子序列：两个单词中都有的序列包含的字母数，最后求得的子序列长度越长，说明两个单词越相似

算法的步骤如下：
在这里插入图片描述

计算FOSH与FISH与FORT两个单词的最长公共子序列的过程与结果如下：

在这里插入图片描述

通过上述结果可看出，FISH与FOSH更像一些。

4. 总结

动态规划的实际应用包括如下场景：

  • 生物学家根据最长公共序列来确定DNA链的相似性，进而判断度两种动物或疾病有多相似。

  • 前面讨论了字符串的相似程度。 编辑距离（ levenshtein distance）指出了两个字符串的相
    似程度，也是使用动态规划计算得到的。编辑距离算法的用途很多，从拼写检查到判断用户上传的资料是否是盗版，都在其中。

  • Microsoft Word等具有断字功能的应用程序，使用动态规划确定在什么地方断
    字以确保行长一致。

这篇关于算法快学笔记（十六）：动态规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/708329。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
第10章 中断和动态时钟显示

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用： 为了更好的利用处理器的性能。协同快速和慢速设备一起工作
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
动态规划---打家劫舍

动态规划---打家劫舍

题目： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 思路： 动态规划五部曲： 1.确定dp数组及含义 dp数组是一维数组，dp[i]代表
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
软考系统规划与管理师考试证书含金量高吗？

软考系统规划与管理师考试证书含金量高吗？

2024年软考系统规划与管理师考试报名时间节点： 报名时间：2024年上半年软考将于3月中旬陆续开始报名 考试时间：上半年5月25日到28日，下半年11月9日到12日 分数线：所有科目成绩均须达到45分以上（包括45分）方可通过考试 成绩查询：可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间：预计在11月左右 证书领取时间：一般在考试成绩公布后3~4个月，各地领取时间有所不同
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2