动态规划总结和习题

1、动态规划总结和习题动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择； 而分治法中的各个子问题是独立的（即不包含公共的子问题），因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。不足之处：如果当前选择可能要依赖子问

2、题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。 解决上述问题的办法是利用动态规划。动态规划方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优（最大或最小）值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，（亦即各子问题可包含公共的子问题）也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。W

3、先生每天驾车去公司上班。W先生的住所位于A，公司位于F，图中的直线段代表公路，交叉点代表路口，直线段上的数字代表两路口之间的平均行驶时间。现在W先生的问题是要确定一条最省时的上班路线。习题12022-4-8第6章 动态规划法Page 5习题2用动态规划算法求解下面的组合优化问题： max g1(x1)+g2(x2)+g3(x3) x1+x2+x3=3 x1,x2,x3为非负整数其中g1(x)、g2(x)、g3(x)的值在下表中x xg g1 1(x)(x)g g2 2(x)(x)g g3 3(x)(x)02581410132716173112022习题3设有n种不同面值的硬币，第i种硬币的币值

4、是vi（其中v1=1），重量是wi。现在购买总价值为y的某些商品，需要用这些硬币付款，如果每种钱币使用的个数不限，问如何选择付款的方法使得付出钱币的总重量最轻？1、用合适的数学模型描述问题2、使用以下的输入实例求解问题 1 2 3 4vi 1 4 6 8wi 1 2 4 6 y=11问题描述：在数字序列问题描述：在数字序列A=a1, a2, , an中按递增中按递增下标序列下标序列(i1, i2, ik)（1i1 i2 ikn）顺序选）顺序选出一个子序列出一个子序列B，如果子序列，如果子序列B中的数字都是严格中的数字都是严格递增的，则子序列递增的，则子序列B称为序列称为序列A的递增子序列。最的

5、递增子序列。最长递增子序列问题就是要找出序列长递增子序列问题就是要找出序列A的一个最长的一个最长的递增子序列。的递增子序列。最最长递增子序列问题长递增子序列问题 2022-4-8第6章 动态规划法Page 8最长递增子序列问题最长递增子序列问题想法想法设序列设序列A=a1, a2, , an最长递增子序列是最长递增子序列是B=b1, b2, bm最长递增子序列问题满足最优性原理。最长递增子序列问题满足最优性原理。 设设L(n)为数字序列为数字序列A=a1, a2, , an的最长递增子的最长递增子序列的长度，显然，初始子问题是序列的长度，显然，初始子问题是a1，即，即L(1)=1。考虑原问题的

6、一部分，设考虑原问题的一部分，设L(i)为子序列为子序列A=a1, a2, , ai的最长递增子序列的长度，则满足如下的最长递增子序列的长度，则满足如下递推式：递推式： 1 i = 1或不存在或不存在ajai（1ji）maxL(j) + 1 对于所有的对于所有的ajai（1ji）L(i) =2022-4-8第6章 动态规划法Page 9于序列于序列A=5, 2, 8, 6, 3, 6, 9, 7，用动态规划法求，用动态规划法求解最长递增子序列。解最长递增子序列。首先计算初始子问题，可以直接获得：首先计算初始子问题，可以直接获得：L(1)=1(5)然后依次求解下一个阶段的子问题，有：然后依次求解

7、下一个阶段的子问题，有：L(2)=1(2)L(3)=maxL(1)+1, L(2)+1=2(5, 8, 2, 8)L(4)= maxL(1)+1, L(2)+1=2(5, 6, 2, 6)L(5)=L(2)+1=2(2, 3)L(6)=maxL(1)+1, L(2)+1, L(5)+1)=3(2, 3, 6)L(7)=maxL(1)+1, L(2)+1, L(3)+1, L(4)+1, L(5)+1, L(6)+1=4(2, 3, 6, 9)L(8)=maxL(1)+1, L(2)+1, L(4)+1, L(5)+1, L(6)+1=4(2, 3, 6, 7)序列序列A的最长递增子序列的长度为的最长递增子序列的长度为4，有两个最长递增子序列，分别是，有两个最长递增子序列，分别是2, 3, 6, 9和和2, 3, 6, 7)。最长递增子序列问题最长递增子序列问题实例实例2022-4-8第6章 动态规划法Page 10序号12345678序列元素52