算法设计与分析复习(5)

5/8 给定n 种物品和一背包。物品i 的重量是wi ，其价值为vi ，背包的容量为C 。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

即m(i ，j)是背包容量为j ，可选择物品为i ，i+1，…，n 时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i ，j)的递归式如下。 i

i i i w j w j j i m v w j i m j i m j i m <≤≥⎩⎨⎧++-++=0),1(}),1(),,1(max{),( n

n n w j w j v j n m <≤≥⎩⎨⎧=00),( 算法复杂度分析：

从m(i ，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c 很大时，算法需要的计算时间较多。例如，当c>2n 时，算法需要Ω(n2n )计算时间。

第4章 贪心算法

4.1 活动安排问题

掌握算法GreedySelector()

4.2 贪心算法的基本要素

1.贪心选择性质

贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素。

动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。

2.最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

掌握背包问题的贪心算法Knapsack 。

4.5 单源最短路径

掌握Dijkstra 算法思想，复杂度分析。

⎪⎩⎪⎨⎧≤≤∈≤∑=n

i x C x w i n i i i 1},1,0{1∑=n

i i

i x v 1max