/gc-algorithm-course

gc algorithm course 2014

Primary LanguageC++

GC Algorithm Course 2014

11月6日 八种排序算法

文件:sort.cpp

其实是数据结构课程设计交的作业

  • 冒泡排序 O(n^2)

  • 选择排序 O(n^2)

  • 插入排序 O(n^2) — 对于基本有序的数列效率最高

  • 希尔排序 O(nlogn) — 插入排序的优化

  • 归并排序 O(nlogn) — 需要额外的空间存储

  • 快速排序 O(nlogn ~ n^2) — 最常用,但对有序数列严重退化

  • 堆排序 O(nlogn) — 璐神讲过,是否再讲?—— 还是讲了-_-||

  • 基数排序 — 简单了解即可,不常用

稳定的:冒泡、插入、归并,其它不稳定
小练习
求逆序对数:
给一列数a1,a2......an,求它的 逆序对数,即有多少个有序对 (i,j),使得i < j 但 ai > aj


第k小数:
输入n个整数和一个正整数k(1 <= k <= n), 输出这些整数从小到大排序后的第k个 

11月13日 & 11月20日 动态规划

斐波那契数列
f(n) = f(n-1) + f(n-2)
普通写法:递归
动态规划写法:自底向上,空间换时间
有时空间也可以省
二项式系数/排列组合: C(n, k) = C(n-1, k-1) + C(n-1, k)
for i : 0 -> n
 	for j : 0 -> min(i, k)
     	 if j = 0 or j = i
        	   c[i][j] = 1
      	else c[i][j] = c[i-1][j-1] + c[i-1][j]
数塔问题

https://oj.leetcode.com/problems/triangle/

d(i, j) = a(i, j) + min{d(i+1, j), d(i+1, j+1)}
d(j) = a(i, j) + min{d(j), d(j+1)}

—重叠子问题的记忆化搜索 — 画图更能直观理解(树)
最大子序列

https://oj.leetcode.com/problems/maximum-subarray/

if A[i] > A[i] + A[i-1]     A[i] = A[i]
else      A[i] = A[i] + A[i-1]

11月20日 动态规划 continue

解码问题

https://oj.leetcode.com/problems/decode-ways/

边界条件的考虑!!!
if s[i] == 0 and s[i-1] != 1 and s[i-1] != 2 : return 0
else if s[i] == 0 : dp[i] = dp[i-2]
else if s[i-1] == 1 || s[i-1] == 2 && s[i] = 1~6 : dp[i] = dp[i-1] + dp[i-2]
else dp[i] = dp[i-1]
背包问题

有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。 f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值

0-1背包:

f[i][v] = max(f[i-1][v], f[i-1][v-c[i]] + w[i])
优化空间复杂度:
for i 0 -> N
	 for v V -> 0
    	  f[v] = max(f[v], f[v-c[i]] + w[i])

初始化的细节:

  1. 背包恰好装满:f[0] = 0, f[1 ~ V] = -oo

  2. 不要求背包装满:全部初始化为0

如果要求背包恰好装满,那么此时只有容量为0的背包可能被价值为0的nothing“恰好 装满”,其它容量的背包均没有合法的解,属于未定义的状态,它们的值就都应该是−∞了。如果 背包并非必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的价值为0, 所以初始时状态的值也就全部为0了

完全背包:

令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值

f[i][v] = max{f[i-1][v], f[i − 1][v − k × c[i]] + k × w[i]}      0 <  k × c[i] < v

一个很简单有效的优化,是这样的:若两件物品i、j满 足c[i] < c[j]且w[i] > w[j],则将物品j去掉,不用考虑

for i 0 -> N
	 for v 0 -> V
    	  f[v] = max(f[v], f[v-c[i]] + w[i])

混合背包: k 的取值在其给定的范围内即可

练习:

http://acm.hdu.edu.cn/showproblem.php?pid=2602 http://acm.hdu.edu.cn/showproblem.php?pid=1114 http://acm.hdu.edu.cn/showproblem.php?pid=2191

总结:
与分治法的相同和不同点, 相比递归:
  • 优势:避免了对同一个子问题多次求解
  • 劣势:可能会对一些不必要的子问题求解
特点:
  • 最优化
  • 无后效性
  • 有重叠子问题
求解步骤
  1. 划分阶段
  2. 确定状态和状态变量 — 必须满足无后效性
  3. 状态转移方程
  4. 寻找边界条件

核心:状态转移方程 注意:边界条件