算法设计与分析 - 总结0

放入背包中的物品的求解过程：则65表示把5个物品放入容量为6的背包中的最大价值和。 i=5,j=6; v[5][6]>v[4][6],x[5]=1, j=6-w[5]=1 i=4,j=1; v[4][1]=v[3][1], x[4]=0

i=3,j=1; v[3][1]>v[2][1], x[3]=1, j=1-w[3]=0 i=2,j=0; v[2][1]=v[1][0], x[2]=0 i=1,j=0; v[1][0]=v[0][0], x[1]=0 结果是把第3个和第5个放入了背包

掌握最长公共子序列问题的动态规划法算法及具体实现（P126-128），习题6-4

求X=“xzyzzyx”和Y=“zxyyzxz”序列的最长公共子序列的动态规划函数为：

L[i][j]表示X中前i个元素和Y中前j个元素构成的序列的最长公共子序列的长度。 为了确定具体的最长公共子序列，需要同时计算S[i][j]的值，S[i][j]表示在计算L[i][j]的过程中的搜索状态。

子序列为斜箭头所标示的行或列：X[2],X[3],X[6] ,X[7]或Y[1], Y[3], Y[4] , Y[6]最长公共子序列的长度为4 即为：zyyx

第7章 贪心法

了解贪心法的设计思想

贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出局部最优选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。 贪心法的关键在于决定贪心策略。

掌握可以用贪心法解决的问题：

TSP问题中的两种解决方法：最近领点策略，最短链接策略

最小生成树问题的两种算法：最近顶点策略（Prim算法），最短边策略（Kruskal算法） 背包问题，活动安排问题，多机调度问题，哈夫曼编码。

掌握最小生成树的两种贪心算法：prim算法和kruskal算法（P145-148），给出具体的例子，能够用两种方法画出树的生成过程。

掌握背包问题的贪心算法（P148-151），给出一个具体的例子，能够写出解决问题的过程。习题7-2 问题：求如下背包问题的最优解：有7个物品，价值P=(10,5,15,7,6,18,3),重量w=(2,3,5,7,1,4,1),背包容量W=15. 解决方法： 先对物品的单位重量价值按照降序排列 物品重量 物品价值 物品价值/物品重量 1 2 4 5 1 3 7 6 10 18 15 3 5 7 6 5 4.5 3 3 1.67 1 依次把物品放入容量为15的背包，直到背包被装满 1+2+4+5+1=13，前5个物品装入背包，还剩下容量为2，第6个物品只能装入2/3 所以总价值为：6+10+18+15+3+5*2/3=55.3333