动态规划总结和习题.pptx

动态规划总结和习题
动态规划的实质是分治思想和解决冗余,因此,动态规划是一种将问题实例分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略。
由此可知,动态规划法与分治法和贪心法类似,它们都是将问题实例归纳为更小的、相似的子问题,并通过求解子问题产生一个全局最优解。
贪心法的当前选择可能要依赖已经作出的所有选择,但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下,一步一步地作出贪心选择;
而分治法中的各个子问题是独立的(即不包含公共的子问题),因此一旦递归地求出各子问题的解后,便可自下而上地将子问题的解合并成问题的解。
不足之处:如果当前选择可能要依赖子问题的解时,则难以通过局部的贪心策略达到全局最优解;如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题。解决上述问题的办法是利用动态规划。
动态规划方法主要应用于最优化问题,这类问题会有多种可能的解,每个解都有一个值,而动态规划找出其中最优(最大或最小)值的解。若存在若干个取最优值的解的话,它只取其中的一个。在求解过程中,该方法也是通过求解局部子问题的解达到全局最优解,但与分治法和贪心法不同的是,动态规划允许这些子问题不独立,(亦即各子问题可包含公共的子问题)也允许其通过自身子问题的解作出选择,该方法对每一个子问题只解一次,并将结果保存起来,避免每次碰到时都要重复计算。
W先生每天驾车去公司上班。W先生的住所位于A,公司位于F,图中的直线段代表公路,交叉点代表路口,直线段上的数字代表两路口之间的平均行驶时间。现在W先生的问题是要确定一条最省时的上班路线。
A 3 B1 4 C1
4 5 3
B2 2 C2 3 D1
1 2 3
C3 4 D2 5 F
习题1
2017/11/13
第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
g1(x)
g2(x)
g3(x)
0
2
5
8
1
4
10
13
2
7
16
17
3
11
20
22
习题3
设有n种不同面值的硬币,第i种硬币的币值是vi(其中v1=1),重量是wi。现在购买总价值为y的某些商品,需要用这些硬币付款,如果每种钱币使用的个数不限,问如何选择付款的方法使得付出钱币的总重量最轻?
1、用合适的数学模型描述问题
2、使用以下的输入实例求解问题
1 2 3 4
vi 1 4 6 8
wi 1 2 4 6
y=11
问题描述:在数字序列A={a1, a2, …, an}中按递增下标序列(i1, i2,…, ik)(1≤i1< i2<…< ik≤n)顺序选出一个子序列B,如果子序列B中的数字都是严格递增的,则子序列B称为序列A的递增子序列。最长递增子序列问题就是要找出序列A的一个最长的递增子序列。
最长递增子序列问题
2017/11/13
第6章动态规划法
Page 8
最长递增子序列问题——想法
设序列A={a1, a2, …, an}
最长递增子序列是B={b1, b2,…, bm}
最长递增子序列问题满足最优性原理。
设L(n)为数字序列A={a1, a2, …, an}的最长递增子序列的长度,显然,初始子问题是{a1},即L(1)=1。考虑原问题的一部分,设L(i)为子序列A={a1, a2, …, ai}的最长递增子序列的长度,则满足如下递推式:
1 i = 1或不存在aj<ai(1≤j<i)
max{L(j) + 1} 对于所有的aj<ai(1≤j<i)
L(i) =
2017/11/13
第6章动态规划法
Page 9
于序列A={5, 2, 8, 6, 3, 6, 9, 7},用动态规划法求解最长递增子序列。
首先计算初始子问题,可以直接获得:
L(1)=1({5})
然后依次求解下一个阶段的子问题,有:
L(2)=1({2})
L(3)=max{L(1)+1, L(2)+1}=2({5, 8}, {2, 8})
L(4)= max{L(1)+1, L(2)+1}=2({5, 6}, {2, 6})
L(5)=L(2)+1=2({2, 3})
L(6)=max{L(1)+1, L(2)+1, L(5)+1)}=3({2, 3, 6})
L(7)=max{L(1)+1, L(2)+1, L(3)+1, L(4)+1, L(5)+1, L(6)+1}=4({2, 3, 6, 9})
L(8)=max{L(1)+1, L(2)+1, L(4)