c语言背包问题_背包问题 贪心算法_c语言背包问题csdn(2)

这里的重叠子结构是S[1...i]，T[1...j]。

以下是相应代码。考虑到C语言数组下标从0开始，做了一个转化将字符串后移一位。

应用：

(1)子串匹配

难度评级：★★

修改两处即可进行子串匹配：

如果j= strlen(S) - strlen(T)，那么说明T是S的一个子串。

（这部分是根据《算法设计手册》8.2.4和具体实例Skiena与Skienaa、Skiena与somta的分析获得的，解释不够全面，可能有误，请注意）

(2)最长公共子序列

难度评级：★★

将match时不匹配的代价转化为最大长度即可：

此时，最小值是两者不同部分的距离。

（这部分同样也不好理解，对于最长公共子序列，建议直接使用下一部分中的解法）

扩展：

难度评级：★

对于序列S和T，求它们的最长公共子序列。例如X={A,B,C,B,D,A,B}，Y={B,D,C,A,B,A}则它们的lcs是{B,C,B,A}和{B,D,A,B}。求出一个即可。

解法：

和2类似，对于X[1...m]和Y[1...n]，它们的任意一个lcs是Z[1...k]。

(1)如果X[m]=Y[n]，那么Z[k]=X[m]=Y[n],且Z[1...k-1]是X[1...m-1]和Y[1...n-1]的一个lcs；

(2)如果X[m]!=Y[n]，那么Z[k]!=X[m]时Z是X[1...m-1]和Y的一个lcs；

(3)如果X[m]!=Y[n]，那么Z[k]!=Y[n]时Z是X和Y[1...n-1]的一个lcs；

下面是《算法导论》上用伪码描述的lcs算法。其中c[i][j]记录当前lcs长度，b[i][j]记录到达该状态的上一个状态。

扩展1：

如何输出所有的LCS？

难度评级：★★

分析：

根据上面c[i,j]和b[i,j]的构造过程可以发现如果c[i-1,j]==c[i,j-1]，那么分别向上和向左返回的上一个状态都是可行的。如果将其标记为“左/上”并通过递归调用来生成从c[m,n]到c[1,1]的所有路径，就能找出所有的LCS。时间复杂度上界为O(mn)。

扩展2：

通过LCS获得最长递增自子序列。

分析：

对于1个序列，如243517698，最大值9，最小值1，那么通过将它与123456789求LCS得到的就是最长连续递增子序列23568。

这种做法不适用于最长连续非递减子序列，除非能获得重复最多的元素数目，如2433517698，那么可以用112233445566778899与之比较。

使用专门的最长递增子序列算法可以进行优化，详见下一部分。

难度评级：★

对于一个序列如1，-1，2，-3，4，-5，6，-7，其最长第增子序列为1,2,4,6。

解法：

除了利用3中lcs来求解，这里使用求解lis问题的专门方法。

先看看如何确定子结构的表示。对于长度为k的序列s[1...k]，如果用lis[k]记录这个序列中最长子序列似乎没什么用，因为在构造lis[k+1]时，需要比较s[k]与前面长度为lis[k]的lis的最后一个元素、s[1...k]中长度为lis[k]-1的序列的最后一个元素等等，没有提供什么便利，这个方案被否决。

为了将每个lis[k]转化为构造lis[k+1]时有用的数据，把子结构记为以s[k]为结尾的lis的长度，那么对于s[k+1]，需要检查所有在它前面且小于它的元素s[i]，并令lis[k+1] = max(lis[i]+1),（i=1 to k,s[k+1]>s[i]）。这样，一个O(n2)的算法便写成了。为了在处理完成后不必再一次遍历lis[1...n]，可以使用一个MaxLength变量保存当前记录中最长的lis。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-23984-2.html