文档章节

《算法图解》——第九章 动态规划

o
 osc_x4h57ch8
发布于 2018/04/24 13:59
字数 1602
阅读 12
收藏 0

精选30+云产品,助力企业轻松上云!>>>

       第九章    动态规划

1  动态规划——背包问题

公式:

 

练习
9.1 假设你还可偷另外一件商品——MP3播放器,它重1磅,价值1000美元。你要偷吗?

要。在这种情况下,你可偷来MP3播放器和iPhone和吉他,总价值为4500美元

 

行的排列顺序发生变化时结果如何?答案没有变化。也就是说,各行的排列顺序无关紧要。

可以逐行而不是逐列填充网格吗?就这个问题而言,这没有任何影响,但对于其他问题,可能有影响。

增加一件更小的商品将如何呢?你需要考虑的粒度更细,因此必须调整网格。

可以偷走商品的一部分吗?答案是没法处理。使用动态规划时,要么考虑拿走整件商品,要么考虑不拿,而没法判断该不该拿走商品的一部分。但是贪婪算法可以轻松处理!


 

2  旅行行程最大化

根据清单画动态规划网格:

如何处理相互依赖的情况?

动态规划功能强大,它能够解决子问题并使用这些答案来解决大问题。但仅当每个子问题都是离散的,即不依赖于其他子问题时,动态规划才管用。

计算最终的解时会涉及两个以上的子背包吗?

为获得前述背包问题的最优解,可能需要偷两件以上的商品。但根据动态规划算法的设计,最多只需合并两个子背包,即根本不会涉及两个以上的子背包。不过这些子背包可能又包含子背包。

最优解可能导致背包没装满吗?of course

 

练习
9.2 假设你要去野营。你有一个容量为6磅的背包,需要决定该携带下面的哪些东西。其中每样东西都有相应的价值,价值越大意味着越重要:

水(重3磅,价值10);

书(重1磅,价值3)

食物(重2磅,价值9);

夹克(重2磅,价值5);

相机(重1磅,价值6)。

请问携带哪些东西时价值最高?用动态规划做呗,水,食物,相机


 

 

3  最长公共子串

动态规划的启示:

①动态规划可帮助你在给定约束条件下找到最优解。

②在问题可分解为彼此独立且离散的子问题时,就可使用动态规划来解决。

③每种动态规划解决方案都涉及网格。

④单元格中的值通常就是你要优化的值。

⑤每个单元格都是一个子问题,因此你应考虑如何将问题分成子问题,这有助于你找出网格的坐标轴。


 

 

举个🌰:Alex输入了hish,那他原本要输入的是fish还是vista呢?

3.1 绘制网格

解决上面问题的网格应该怎么构建,要考虑下面几点:

①单元格中的值是什么?在这个例子中,你要找出两个单词的最长公共子串,这就是你要计算的值。

②如何将这个问题划分为子问题?你可能需要比较子串:不是比较hish和fish,而是先比较his和fis。

③网格的坐标轴是什么?每个单元格都将包含这两个子串的最长公共子串的长度。这也给你提供了线索,让你觉坐标轴很可能是这两个单词。

因此,网格可能类似于下面这样:

3.2 填充网格

填充时用什么公式呢?费曼算法(Feynman algorithm)步骤如下:(这怕不是再说废话= =!废慢算法?)

①将问题写下来

②好好思考

③将答案写下来

3.3 揭晓答案

查找单词hish和vista的最长公共子串时,网格如下:

对于背包问题,最终答案总在最后的单元格中;但对于最长公共子串而言,答案是网格中最大的数字——不一定在最后的单元格中。

那么问题的答案出来了,hish和fish的最长公共子串包含三个字母,而hish和vista的最长公共子串包含两个字母。因此Alex很可能原本要输入的是fish。

3.4 最长公共子序列

假设Alex不小心输入了fosh,他原本想输入的是fish还是fort呢?我们使用最长公共子串公式来比较它们:

所以都为2,长度相同,但是fosh和fish更像。

这里应该比较最长公共子序列两个单词中都有的序列包含的字母数

3.5 最长公共子序列之解决方案

上图的公式:

 

动态规划的实际应用:

生物学家根据最长公共序列来确定DNA链的相似性,进而判断度两种动物或疾病有多相似。最长公共序列还被用来寻找多发性硬化症治疗方案。

你使用过诸如 git diff 等命令吗?它们指出两个文件的差异,也是使用动态规划实现的。

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

你使用过诸如Microsoft Word等具有断字功能的应用程序吗?它们如何确定在什么地方断字以确保行长一致呢?使用动态规划!

 

 

练习
9.3 请绘制并填充用来计算blue和clues最长公共子串的网格。


 

 

4  小结

①需要在给定约束条件下优化某种指标时,动态规划很有用。

②问题可分解为离散子问题时,可使用动态规划来解决。

③每种动态规划解决方案都涉及网格。

④单元格中的值通常就是你要优化的值。

⑤每个单元格都是一个子问题,因此你需要考虑如何将问题分解为子问题。

⑥没有放之四海皆准的计算动态规划解决方案的公式。

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

会议通知 | 2020中国计算与认知神经科学会议

关于大会关于 计算神经科学以神经生物实验为基础,以建立数学模型,开展计算模拟和分析作为基本手段,来刻画和描述大脑的神经活动,探究神经系统各种复杂活动和认知功能包括注意、学习、记忆...

脑机接口社区
06/02
20
0
大神分享快3怎么算下期和值

大神分享快3怎么算下期和值{叩67790572}使用的标签:constructor-arg标签出现的位置:bean标签的内部标签中的属性type:用于指定要注入的数据的数据类型,该数据类型也是构造函数中某个...

yiren081
25分钟前
21
0
Matlab系列之运算符和标点符号的功能介绍

本来月初就打算接着写的,但是电脑不小心进水,主板什么的都废了,周末才找时间拿去修好,心塞。 就不多讲太多废话了,开始分享今天的内容,对MATLAB的运算符做个介绍,然后再对标点符号进行...

狂人V
07/06
9
0
Java源码系列(1):Comparable和Comparator的区别

在讲Comparable和Comparator区别之前,先补充一个知识点。 先看代码: Person类 1public class Person<T> { 2  private T id; 3 4  public T getId() { 5    return i...

学习Java的小姐姐
2018/09/19
25
0
ThreadPoolTaskScheduler手写调度中心

先贴一个自己写的demo把,原理其实就是这样的。 CronTrigger这个类可以将cron表达式转换成Date,可以查看schedule源码学到不少东西,下面代码就是转换成下一执行时间。 public Date nextEx...

朝如青丝暮成雪
46分钟前
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部