第5章动态规划PPT课件

1、第第5章章 动态规划动态规划5.3 定期多阶段决策问题定期多阶段决策问题2021-12-14山东大学 软件学院2阶段数固定的多阶段决策问题背包问题背包问题最长公共子序列问题最长公共子序列问题旅行售货员问题旅行售货员问题 2021-12-14山东大学 软件学院3背包问题背包问题（背包问题（The Knapsack Problem）实例：有一个背包，总承重为整数实例：有一个背包，总承重为整数 W。有有 n 个物品，每个物品重量为个物品，每个物品重量为 wi，价值为，价值为 vi，i = 1.n。wi和和vi 均为整数。均为整数。目标：装入背包若干物品，使其总重量不超过目标：装入背包若干物品，使其总

2、重量不超过 W，总价值，总价值最大。最大。2021-12-14山东大学 软件学院4例子2021-12-14山东大学 软件学院5解（1）2021-12-14山东大学 软件学院6动态规划表时间复杂度以上动态规划法的时间复杂度为以上动态规划法的时间复杂度为O(nW)。这个时间复杂度不是多项式的，原因在于这个时间复杂度不是多项式的，原因在于W是问题输入中是问题输入中的一个整数。的一个整数。2021-12-14山东大学 软件学院72021-12-14山东大学 软件学院8解（2）2021-12-14山东大学 软件学院9例子2021-12-14山东大学 软件学院10最长公共子序列（LCS）问题最长公共子序列

3、（最长公共子序列（Longest Common Subsequence）问题）问题实例：序列实例：序列 X = x1x2xm，Y = y1y2yn。询问：询问：X 和和 Y 的一个最长公共子序列。的一个最长公共子序列。子序列：若有子序列：若有 l 个数满足个数满足1 s1 s2 sl n，则称，则称 xs1xs2xsl 为为 X 的一个子序列。的一个子序列。2021-12-14山东大学 软件学院11递推公式2021-12-14山东大学 软件学院12例子2021-12-14山东大学 软件学院13Algorithm LCS(X, Y)计算计算X = x1x2.xm和和Y = y1y2.yn的最长公

4、共子序列。的最长公共子序列。 1 for i 1 到到 m do 2 ci, 0 0。 3 endfor 4 for j 0 到到 n do 5 c0, j 0。 6 endfor 7 for i 1 到到 m do 8 for j 1 到到 n do 9 if xi = yj then10 ci, j ci 1, j 1 + 1。LCS之动态规划算法2021-12-14山东大学 软件学院14LCS之动态规划算法11 fi, j “ ”。12 else13 if ci 1, j ci, j 1 then14 ci, j ci 1, j。15 fi, j “ ”。16 else17 ci, j

5、ci, j 1。18 fi, j “”。19 endif20 endif21 endfor22 endfor23 return c, f。时间复杂度以上动态规划法（以上动态规划法（LCS问题）的时间复杂度为问题）的时间复杂度为O(mn)。这是一个多项式的时间复杂度，表明这是一个多项式的时间复杂度，表明LCS问题是多项式时问题是多项式时间可解的。间可解的。2021-12-14山东大学 软件学院152021-12-14山东大学 软件学院16旅行售货员（TSP）问题旅行售货员问题是图论中一个著名问题。旅行售货员问题是图论中一个著名问题。实例：图实例：图G = (V, E)，每条边，每条边(vi, v

6、j)上有长度上有长度d(vi, vj)。询问：找一个最短的圈，走过所有的顶点。询问：找一个最短的圈，走过所有的顶点。等价描述：从等价描述：从v1点出发，经过其余顶点（点出发，经过其余顶点（v2, , vn）各一次，）各一次，最后返回最后返回v1的最短的圈。的最短的圈。2021-12-14山东大学 软件学院17递推方程2021-12-14山东大学 软件学院18例5.3.12021-12-14山东大学 软件学院19例5.3.12021-12-14山东大学 软件学院20计算一个单元格fk(vi, U, v1) 1 d 。 2 for each vj U do 3 t d(vi, vj) + table(vj, U vj)。 4 if t d then d t。 5 endfor 6 return d。2021-12-14山东大学 软件学院21计算过程2021-12-14山东大学 软件学院22计算过程2021-12-14山东大学 软件学院23一般