算法设计与分析之动态规划问题和具体实例-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法设计与分析之动态规划问题和具体实例。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划（Dynamic Programming,DP）算法通常用于求解某种具有最优性质的问题。在这类问题中，可能会有许多可行解，每一个解都对应一个值，我们希望找到具有最优值的解。
动态规划算法与分治法类似，其基本思想也是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解中得到原有问题的解。与分治法不同的是，动态规划经分解后得到的子问题往往不是相互独立的。

课后题链接

链接：https://pan.baidu.com/s/1IhBb_RJWiKJ9lejRW-o12Q?pwd=mioj
提取码：mioj
--来自百度网盘超级会员V4的分享

因为评论不能发链接（CSDN限制）回答学弟的请求。

一.01背包问题

1.问题定义:

i个物品 j的容量利用给定的容量w来装使总体具有最大价值的物品

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

2.蛮力策略：

尽可能挑选价值大的物品先放尽可能挑选体积小的物品先放穷举所有的可能

显然这些都不是最高效的

建立模型

虽然穷举所有的可能不是最高效的算法但是相比于前两种他一定能得到最优解

利用计算机我们建立递归式

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

KnapsackSR(h,i,c)//(h,i)代表选取范围比如(1,5)表示从第1到第5个物品进行考量 c代表背包剩余容量建立递归树后我们发现 h(1,n,c) 和 h(1,n-1,c-cn)有一些关系

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

我们假设从第一次开始每次选的都是优化解我们想当我们已经挑选完前i-1个物品之后会得到一个优化解KnapsackSR(h,i-1,c)这个时候我们当成第i个物品是最后一个物品

1.如果容量足够装下第i个物品时我们自然会让这个物品装入背包

2.但是当容量不足的时候不能装入背包的时候这时第i个的优化解就是i-1的优化解

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

但是我们发现这种递归的策略是不是很麻烦时间复杂度是指数次方

举个简单的例子如上图每个商品的体积都是v 那么相同颜色的代表同一类子问题

就好比说一条路站点ABCDE 我要一个助手去这四个地点取快递我先让助手去B地点取快递取完之后我打电话让去A地取快递然后再去C取快递那么我们发现重复了B这条路径我们是否要合理分配一站式服务呢？

3.优化理论

前言:

既然子问题有重叠避免重复递归调用我们采用记忆式递归就是把结果记忆下来当需要的时候直接调用

优化子结构

定义:就是问题和子问题具有相互依赖关系

01优化子结构:

子问题的重叠性

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

建立递归方程

m(i,j):从第一个物品考量到第i个物品时,背包的容量是j m(i,j)背包的总价值

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

之后建立我们的递归方程:

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

自底向上问题的具体求解过程

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

建立记忆化递归数组

求解过程: 我们想知道当容量为c时考量第一个物品时的最大价值m(1,c) 需要借助max{m(2,c-wi)第一个物品放进去，m(2,c)第一个物品不放进去（容量不够) 我们想知道m(2,c)需要知道第二个物品放没放进去我们想知道m(2,c-wi）需要直到第二个物品放没放进去(3,c-w1-w2)/(3,c-w1）第二个物品没放进去............直到推演到最后一行

实际操作和记忆化递归恰好相反我们可以得到的是当考量到第n个物品之后背包的容量也就是数组的最后一行我们可以根据背包是否放入的不同组合来穷举最后的情况类似于编码背包放入就是1,不放入就是0 最后一行代表能够放下的所以能装下的排列组合

计算方法只能是自下而上自左至右的来计算

伪代码:

n代表一共有多少的物品
for j = 0 to min(wn-1,c)//如果wn不能放下 那么最后一行的价值就是
	do m[n,j] = 0
for j = wn to c        //如果wn能放下那么 最后一行的价值就是wn 的价值
	do m[n,j-wn] = vn
for i<--n-1 to 2 
	for j = 0 to min(wi-1,c) do//这一部分时背包容量不够的部分 代表wn不能装进去
		m[i,j] = m[i+1,j]//如果背包容量不够 那么,[i,j] = m[i+1,j]
	for j = wi to C do:
m[i, j] = max{ m[i + 1,j - wi] + vi,m[i + 1,j] }

/*最后一部考量到最后一个物品一号物品*/

if c<w1
	m[1,c] = m[2,c]
else
m[1, c] = max{ m[2,c - w1] + v1 , m[2,c] }

实例(example):实例化分析&&实例化讲解&&理论巩固

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

算法步骤描述:

首先初始化最后一行数组

紧接着从第n-1行到第二行循环求解m[i,j] = 他的下一行正下方和本身决定

m[i,j] = max {m[i+1,j-wi] + vi, m[i+1,j]} 就是看能不能装下了

理论基础 (为啥这么做): have a review 回顾优化子结构的一个定理

最后一行枚举了各种情况已经是各种的优化解那么套用引理(yi,......yn)也是优化解

根据递归 yn-1-yn 也是 yn-2-yn-0/1*wn-2的优化解

二.最长公共子序列问题

1.问题定义:

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

2 优化方法

分析

递归算法&子问题重叠

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

蛮力枚举的方法我们不做过多解释下面我们来分析他为啥可以用动态和规划

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

不难发现长度为4和长度为3之间存在联系那么也不难探索一下这个问题是否具有优化子结构

规定:

c[i,j]表示X串第i个位置和Y串第j个位置的最长公共子序列

分两种情况讨论两个指针所在位置相等和不相等

我们先来讨论不相等的情况

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

不相等的话分两种情况然后取他俩的最大值

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

依赖于两个子问题所以具有优化子结构

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

如果两个相等的话那么两个指针向后移动并让最长公共子序列+1

递推式的建立

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

求解过程

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

时间复杂度o(m*n)

算法实例

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

上图为记忆化递归矩阵

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

我们来看一下求解过程

首先定义两个数组c[]和rec[] c【】记录最长公共前后缀长度 rec数组记录和前面的依赖关系也就是根据哪个方向相邻的数组推导出来的

首先初始化c[0,i]和c[j,0]令他们都是0 当判断到c[1,1]时 ,发现x1 和 y1不相等那么我们调用递归式就是max{c[1,0],c[0,1]} 发现都是0 所以c[1,1]就是0

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

前几个都是u就是来自上方当遍历到c[1,4]是 = c[0,3]+1 LU表示他来自左上方

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

利用规则反复迭代我们可以得到正确的结果

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

一定要动手计算！！！

算法伪代码

l1 <- len(X)
l2 <- len(Y)
for i = 0 to l1 do
    c[i,0] = 0
for j = 0 to l2 do
    c[0,j] = 0
for i = 1 to l1
    for j = 1 to l2
        if xi = yj
            c[i,j] = c[i-1,j-1] +1
        else
            c[i,j] = max{c[i,j-1],c[i-1,j}
return c

三矩阵链乘代价问题

1.问题定义

定义矩阵的代价 o(pqr)

不同的矩阵结合顺序会使代价不同读者可以尝试用几种不同的矩阵按不同的次序进行相乘

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

2.问题分析

1.优化子结构

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

证明方法是反正法假设不是最优解那么他俩加一起是A1-An最优解不是现在的A1-An与已知矛盾

2.子问题的重叠性

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

3.问题求解

规定

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

求解

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

自顶向上地分析问题&自底向上求解问题

我们想要求出m[1,5] 需要遍历所有的m[1,k] m[k+1,5] k = 1~4

也就是蓝色的所有值不断地递归直到i = j就是终止条件

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

我们从最后一行开始计算 c[1,1] c[2,2] c[3,3] .... 再利用对角线进行扩展 k = i+1 i+2..........

伪代码

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

时间复杂性分析:

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

四.最优二叉搜索树

1.问题定义

最优二叉搜索树的问题的形式可以定义如下：给定一个n个不同关键字的已排序的序列K=<K1,K2,…,Kn>(因此k1<k2…<kn)，我们希望用这些关键字构造一棵二叉树搜索树。对每个关键字ki，都有一个概率pi表示其搜索频率。有些搜索值可能不在K中，因此我们还要有n+1个“伪关键字”d0,d1,d2,…,dn表示不在K中的值。对每个伪关键字di，也都有一个概率qi表示对应的搜索频率。

实例

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

不难发现不同二叉树的形状会影响检索效率

搜索代价的定义

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

2.问题分析

1.优化子结构

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

具体实例

2.子问题的划分规约求和

定理：算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

3.优化函数的递归方程

假设以第k个节点作为根,那么检索代价就是两个子问题的和,也就是,为啥要加上w[i,j]呢,因为合并的过程中加上了原来划分的根节点x_k所以,树的高度增加了1,所以要相加。

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

4.计算方法

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

数据结构

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

伪代码

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

(53条消息) 第十五章动态规划（最优二叉搜索树）_qq_503506954的博客-CSDN博客_若7个关键字的概率如下所示,求其最优二叉搜索树

一些练习

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法 (1)：如果是在第k个位置进行划分合并那么a_1~a_k-1和a_k~a_n也是原问题的最优解

证明:如果子问题不是母问题的最优解则存在一个最优的合并解，与母问题是最优解矛盾

(2):定义 S(i,j) = a_i+.....a_j 定义m[i,j]表示合并a_i到a_j的最大代价

代价方程

m[i,j] = 0 (i=j)
max{m[i,k-1]+m[i,j]}+S[i,j]（i+1<k<j) 在i-j中选取划分

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法

(3)伪代码

Integer-Merge-Order(a1,...,an)
1 for i ← 1 to n //对角线
2 do m[i, i] ← 0, S[i, i] ← ai;
3 for l ← 2 to n //计算l对角线
4 do for i ← 1 to n − l + 1
5 do j ← i + l − 1;
6 S[i, j] ← S[i, j − 1] + aj ;
7 m[i, j] ← −∞;
8 for k ← i + 1 to j
9 do q ← m[i, k − 1] + m[k, j];
10 if q>m[i, j]
11 then m[i, j] ← q,D[i, j] ← k;
12 m[i, j] ← m[i, j] + S[i, j];
13 return m, D;

2.动态规划问题求解集合划分问题

算法设计期末考试最优二叉树例题,# 算法设计与分析,动态规划,算法