动态规划笔记

今日刷NLP,从分词算法中讲到维特比算法,再讲到动态规划算法。

小梳理一下。

 

动态规划算法

动态规划算法,是一种求解最优解问题的算法,其核心三步骤:

1.明确目标

2.定义子问题(阶段状态转移方程)

3.由子问题推出总问题(状态转移)

 

我把目前接触到的分成两类,单参数和双参数:

单参数(线状):斐波那契数列,最大子序列和,最长递增子序列,零钱兑换,有向图的最短路径问题,等等

双参数(表格状):0-1背包问题,编辑距离(计算单词之间相似度)

 

0-1背包举例:

一、目标

给定若干物品的重量和价值,给定背包大小可装总重量。求可装价值最大多少

二、分析&子问题

把问题拆解,背包大小只有1,物品也只有1个,这个子问题就变成了:如果物品可装下,那么就判断装下后价值大还是不装价值大即可。

复杂化的过程:就是背包大小逐渐递增,物品数量也逐步增多。

行:物品[1...i]     列:背包重量[1...j]

阶段状态转换方程:F[前i件物品,背包大小]

F[i,j]=max(  F(i-1,j)   ,   F(i-1,j-wi)+vi)

三、代码实现如下:

1

发表评论

电子邮件地址不会被公开。 必填项已用*标注

微信扫一扫

微信扫一扫

微信扫一扫,分享到朋友圈

动态规划笔记
嘿!有什么能帮到您的吗?
返回顶部

显示

忘记密码?

显示

显示

获取验证码

Close