存档

文章标签 ‘滚动数组’

最长公共子序列(Longest-Common-Subsequence,LCS)

2012年6月12日 6 条评论

---

一个字符串S,去掉零个或者多个元素所剩下的子串称为S的子序列。最长公共子序列就是寻找两个给定序列的子序列,该子序列在两个序列中以相同的顺序出现,但是不必要是连续的。

例如序列X=ABCBDAB,Y=BDCABA。序列BCA是X和Y的一个公共子序列,但是不是X和Y的最长公共子序列,子序列BCBA是X和Y的一个LCS,序列BDAB也是。

寻找LCS的一种方法是枚举X所有的子序列,然后注意检查是否是Y的子序列,并随时记录发现的最长子序列。假设X有m个元素,则X有2^m个子序列,指数级的时间,对长序列不实际。

使用动态规划求解这个问题,先寻找最优子结构。设X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>为两个序列,LCS(X,Y)表示X和Y的一个最长公共子序列,可以看出

  1. 如果xm=yn,则LCS ( X,Y ) = xm + LCS ( Xm-1,Yn-1 )。
  2. 如果xm!=yn,则LCS( X,Y )= max{ LCS ( Xm-1, Y ), LCS ( X, Yn-1 ) }

LCS问题也具有重叠子问题性质:为找出X和Y的一个LCS,可能需要找X和Yn-1的一个LCS以及Xm-1和Y的一个LCS。但这两个子问题都包含着找Xm-1和Yn-1的一个LCS,等等.

阅读全文...

完全背包

2012年6月11日 5 条评论

---

前面回顾了01背包,在此基础上本节回顾完全背包的几种实现形式,主要有以下几方面内容:

==完全背包问题定义 & 基本实现

==完全背包二进制拆分思想

==完全背包使用滚动数组(略)

==完全背包中的逆向思维

==完全背包使用一维数组

========================================

完全背包问题定义 & 基本实现

问题:有个容量为V大小的背包,有很多不同重量weight[i](i=1..n)不同价值value[i](i=1..n)的货物,每种物品有无限件可用,想计算一下最多能放多少价值的货物。

与01背包不同的是,完全背包每件物体可以放入无限件(只要能放的下),故对于每件物品i,相当于拆分成了v/c[i]件相同的物品,拆分之后物品i就不是放入或不放入的两种情况了,而是放入0件、放入1件、放入2件…等情况了,对于该件物品i,最大价值取放入k件的最大值,故状态转移方程为:


f(i,v) = max{ f(i-1,v-k*c[i]) + k*w[i] | 0<=k<=v/c[i] }

各状态的意义不再赘述,上代码,关于复杂度以及每种物品的状态数见代码注释:

阅读全文...

0-1背包

2012年4月30日 3 条评论

---

四月份还没写,不能这么荒废了呀,赶紧水一篇吧,哈哈。前些日子回顾了DP的一些基础,就做一下整理吧,从0-1背包开始。

本节回顾0-1背包的基本模型,关于它的实现有很多种写法,这里对不同实现做个简单列举,主要是写代码练手了,主要有以下几方面内容:

==0-1背包问题定义 & 基本实现

==0-1背包使用滚动数组压缩空间

==0-1背包使用一维数组

==0-1背包恰好背满

==0-1背包输出最优方案

========================================

0-1背包问题定义 & 基本实现

问题:有个容量为V大小的背包,有很多不同重量weight[i](i=1..n)不同价值value[i](i=1..n)的物品,每种物品只有一个,想计算一下最多能放多少价值的货物。

DP的关键也是难点是找到最优子结构和重叠子问题,进而找到状态转移方程,编码就相对容易些。最优子结构保证每个状态是最优的,重叠子问题也即n状态的求法和n-1状态的求法是一样的;DP在实现上一般是根据状态转移方程自底向上的迭代求得最优解(也可以使用递归自顶向下求解)。

回到0-1背包,每个物体i,对应着两种状态:放入&不放入背包。背包的最优解是在面对每个物体时选择能够最大化背包价值的状态。0-1背包的状态转移方程为


f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] }

阅读全文...