数据结构和算法 C语言实现

  第三节 编辑距离 edit distance 第一节 序 斐波那契数列           Fibonacci 第二节 0 1背包问题   0 1 Knapsack Problem 第三节 编辑距离           edit distance 第四节 子集总和           subset sum 第五节 钢条切割            cut rod 第六节 硬币找零            Coin Change 第七节 最长公共子序列           Longest Common Subsequence 第八节 矩阵链式乘法 Matrix Chain Multiplication 第九节 最优游戏策略 Optimal Strategy for a Game 第十节 最优二叉查找树           Optimal Binary Search Tree 第十一节 最长递增子序列 Longest Increasing Subsequence 问题描述 有两个字符串src和dest,通过对字符串进行最少的编辑操作将src转换为dest。 1.insert 2.remove 3.replace 以上所有操作花费均相等。 递归解决方案 从两个字符串的左侧或右侧开始处理所有字符。我们从右侧向左遍历，遍历每对字符有两种可能性。 m: Length of str1 (src string) n: Length of str2 (dest string) 1.如果两个字符串的最后一个字符相同，则无事可做。忽略最后一个字符并获得剩余字符串的计数。因此，我们将递归长度同时减1变为m-1和n-1。 2.否则（如果最后一个字符不同），我们考虑对“ str1”的所有操作，考虑对第一个字符串的最后一个字符的所有三个操作，递归计算所有三个操作的最小开销，并取三个值中的最小值。 1.insert: Recur for m and n-1 2.remove: Recur for m-1 and n 3.replace: Recur for m-1 and n-1 该解决方案的时间复杂度,最坏情况下 O(3^m). int min(int x, int y, int z) { int t = (x &l

  第二节 0 1背包问题   0 1 Knapsack Problem 第一节 序 斐波那契数列           Fibonacci 第二节 0 1背包问题   0 1 Knapsack Problem 第三节 编辑距离           edit distance 第四节 子集总和           subset sum 第五节 钢条切割            cut rod 第六节 硬币找零            Coin Change 第七节 最长公共子序列           Longest Common Subsequence 第八节 矩阵链式乘法 Matrix Chain Multiplication 第九节 最优游戏策略 Optimal Strategy for a Game 第十节 最优二叉查找树           Optimal Binary Search Tree 第十一节 最长递增子序列 Longest Increasing Subsequence 问题描述 给定n个物品的权重(weight)和价值(value/profit)，将这些物品放在容量为W的背包中，以在背包中获得最大的总价值。注意，可以选择重量之和小于或等于背包W的物品。 问题方案 问题是要找到一些子集，以便– 1.子集中所有项目的重量总和应小于或等于背包容量 2.在满足上述条件1的所有子集中，期望的子集是其中其项的总和最大的子集。 例子: Case-1: 数量, n = 4   权重, w[] = 2 3 4 5  价值,  v[] = 3 4 5 6   背包容量, W = 5  背包中获得最大的总价值 = 7  Case-2: n = 3 w[] = 3 2 1 v[] = 5 3 4   W = 5  背包中获得最大的总价值 = 9  Case-3: n = 5 w[] = 1 2 3 2 2 v[] = 8 4 5 4 3   W = 4  背包中获得最大的总价值 = 13 递归解决方案 考虑所有项目子集，并计算所有子集的总权重和价值。仅考虑总权重小于W的子集。从所有此类子集中，选择最大值子集。 最优子结构：要考虑项目的所有子集，每个项目可能有两种情况。 情况1：该项