华师14秋《算法设计与分析》离线作业答案

华师14秋《算法设计与分析》离线作业* r" Q5 ~! s, Y: N

4 R" d& y/ ?# F5 q, m本作业共有5个小题，每题20分，共100分。1 N  X, }" I" N; p! N$ @: Y

+ N% y) L5 N5 d" C, [. A2 t1、什么是动态规划？(简答题，20分)
! b( e8 m7 n; K% Z2、请解释贪心法的基本思想？(简答题，20分)
( ~) P8 x6 h& f6 s3、写出二分查找算法（算法设计，20分）
& m0 C2 c! @0 C4、并用贪心法解决如下背包问题。（算法设计，20分）
3 n+ n/ Q; G4 _1 V# L2 Y% e背包问题：n=3, M=30, (p1,p2,p3) = (20,14,25), (w1,w2,w3)=(20,15,15)
) }# d3 l7 J9 t' H5、已知如下定义的数据结构，请画出它的逻辑示意图，并说明它是何种类型的数据结构。（算法设计，20分）6 Q9 b9 U' u' O, C
DS = <D,R,OP! b) D% w, v% q1 ]5 f/ Q
D = { 1, 2, 3, 4, 5, 6}
( g. [$ S9 a! F; U+ L3 N3 qR = { <1,2, <1,3, <2,3, <3,6, <3,5, <5,4, <6,2, <4,3, <5,6 }3 }! x$ P! z0 T  z' p

5 J' k; |2 j" L1 W$ V# d. _: /+ O1 l+ Z8 [
3 w, K  ?8 ]4 n& i6 U0 t) U