考研复试计算机算法与分析笔记

1：递归算法，分治法，贪心算法，动态规划，基本检索和周游方法，回溯法，并行算法。 递归2：0/1背包问题：背包最大承受重量m，现在有n个物品为质量m1,m2

1：递归算法，分治法，贪心算法，动态规划，基本检索和 周游方法，回溯法，并行算法。 递归 2：0/1背包问题：背包最大承受重量m，现在有n个物品 为质量m1,m2,m3…mn，要从n个物品中挑选若干件，使 放入背包的质量之和为m。（0/1的意思就是，一个物品， 要么取，要么不取）一开始是mn放进容量为m的包中， 如果没满，就把m1到m（n-1）放入容量为m-mn的包中， 如果满了，就放弃mn，查看m（n-1）. knap（m，n），如果mn能放得进去，就进一步考虑knap （m-mn，n-1），如果mn放不进去，就考虑knap（m， n-1） 2：汉诺塔问题： Hanoi(n-1,one,three,two) 先把n-1个盘子从1柱借助3柱移动到2柱子， Move(one,three) 然后把1住上还身下的第n个盘子移到3柱 Hanoi(n-1,two,one,three) 最后把2住上的n-1块盘子借助1柱移动到3柱。 3：自然数拆分：任何一个大于1的自然数都可以划分成若 干个小于n的自然数之和。有n/2种拆分 Split（7）=1+split（6）=2+split（5）=3+split（4）