【算法】算法学习七:动态规划 | 背包问题 | 最长公共子串(含源代码)

这篇具有很好参考价值的文章主要介绍了【算法】算法学习七:动态规划 | 背包问题 | 最长公共子串(含源代码)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、背包问题

背包问题是一种经典的组合优化问题,通常有两个版本:0-1背包问题和无限背包问题。

0-1背包问题是指给定一个背包容量和一组物品,每个物品有自己的重量和价值,要求在不超过背包容量的情况下,选择一些物品放入背包,使得物品的总价值最大化。每个物品只能选择放入或不放入背包,不能进行切割。

无限背包问题是指给定一个背包容量和一组物品,每个物品有自己的重量和价值,要求在不超过背包容量的情况下,选择一些物品放入背包,使得物品的总价值最大化。每个物品可以选择放入背包多次,没有数量限制。

解决背包问题的常见方法是使用动态规划。动态规划的基本思想是将原问题分解为若干子问题,并保存子问题的解,避免重复计算。

对于0-1背包问题,可以使用一个二维数组dp[i][j]表示在前i个物品中选择,且背包容量为j的情况下的最大总价值。递推公式如下:

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

其中,w[i]表示第i个物品的重量,v[i]表示第i个物品的价值。dp[i-1][j]表示不选择第i个物品时的最大总价值,dp[i-1][j-w[i]] + v[i]表示选择第i个物品时的最大总价值。最终的结果为dp[n][C],其中n为物品的个数,C为背包的容量。

对于无限背包问题,可以使用一个一维数组dp[j]表示背包容量为j的情况下的最大总价值。递推公式如下:

dp[j] = max(dp[j], dp[j-w[i]] + v[i])

其中,w[i]表示第i个物品的重量,v[i]表示第i个物品的价值。dp[j]表示在背包容量为j的情况下的最大总价值。最终的结果为dp[C],其中C为背包的容量。

以上是解决背包问题的基本思路和动态规划的递推公式。通过填充相应的表格或数组,可以得到最优解。

二、动态规划

动态规划(Dynamic Programming)是一种解决多阶段决策问题的优化方法,通过将原问题划分为多个子问题,并保存子问题的解,避免重复计算,从而得到最优解。

动态规划一般包括以下步骤:

  1. 定义状态:明确问题的状态,并将问题表示为状态的函数。
  2. 定义状态转移方程:根据问题的状态定义,建立状态之间的递推关系。这个递推关系描述了问题的最优解如何由子问题的最优解得到。
  3. 初始化:确定初始条件,即边界状态的值,为后续状态转移做准备。
  4. 递推计算:按照状态转移方程,从初始状态开始,通过递推计算得到最终的目标状态。
  5. 解决问题:根据目标状态的值,得到问题的最优解。

动态规划通常用于解决最优化问题,如最大值、最小值等。它适用于具有重叠子问题和最优子结构性质的问题,可以通过保存子问题的解来避免重复计算。

在动态规划的实现过程中,可以使用数组、矩阵或其他数据结构来保存子问题的解,以便在需要时进行查找和更新。可以采用自顶向下的记忆化递归方法或自底向上的迭代方法进行求解。

动态规划在算法设计和优化中广泛应用,例如背包问题、最长公共子序列、最短路径等。通过合理地定义状态和状态转移方程,可以高效地解决复杂的问题,并获得最优解。

三、背包问题的Python代码实战

3.1 源代码

def knapsack_dynamic_programming(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if weights[i - 1] <= j:
                dp[i][j] = max(values[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]

    # 构造最优解
    selected_items = []
    i, j = n, capacity
    while i > 0 and j > 0:
        if dp[i][j] != dp[i - 1][j]:
            selected_items.append(i - 1)
            j -= weights[i - 1]
        i -= 1

    return dp[n][capacity], selected_items


# 示例用法
weights = [4, 3, 1]
values = [3000, 2000, 1500]
capacity = 4

max_value, selected_items = knapsack_dynamic_programming(weights, values, capacity)
print("Max Value:", max_value)
print("Selected Items:", selected_items)

输出的结果为:

Max Value: 3500
Selected Items: [2, 1]

3.2 代码逐行解读

def knapsack_dynamic_programming(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

这部分是函数的定义和初始化阶段。knapsack_dynamic_programming函数接受三个参数:物品的重量列表weights,物品的价值列表values和背包的容量capacity。首先,使用len(weights)获取物品数量n。然后,创建一个二维数组dp,其中有n+1行和capacity+1列,并将所有元素初始化为0。

    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if weights[i - 1] <= j:
                dp[i][j] = max(values[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]

这部分是动态规划的核心部分,用于填充二维数组dp。通过嵌套的循环遍历,从第一个物品到第n个物品,以及背包容量从1到capacity的范围。对于每个子问题,如果当前物品的重量weights[i - 1]小于等于当前背包容量j,则可以选择将该物品放入背包中,即计算使用当前物品和剩余容量时的总价值。通过比较选择放入和不放入当前物品的情况下的价值,选择较大的价值作为当前子问题的最优解,并将其存储在dp[i][j]中。如果当前物品的重量大于当前背包容量,则无法将该物品放入背包中,直接继承上一个子问题的最优解,即dp[i - 1][j]

    selected_items = []
    i, j = n, capacity
    while i > 0 and j > 0:
        if dp[i][j] != dp[i - 1][j]:
            selected_items.append(i - 1)
            j -= weights[i - 1]
        i -= 1

这部分用于构造最优解。从填充完dp数组的最后一个元素dp[n][capacity]开始,通过反向追溯,从最后一个子问题开始,判断是否选择了第i个物品。如果选择了第i个物品,则将其索引i - 1添加到selected_items列表中,并将背包容量减去该物品的重量weights[i - 1]。然后,继续追溯到上一个子问题dp[i - 1][j],直到回溯到第一个子问题。这样就得到了选择的物品列表。

    return dp[n][capacity], selected_items

函数最后返回最优解的总价值dp[n][capacity]和被选择的物品列表selected_items。

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8

max_value, selected_items = knapsack_dynamic_programming(weights, values, capacity)
print("Max Value:", max_value)
print("Selected Items:", selected_items)

这部分是示例用法。定义了一个具体的问题实例,其中有四个物品,对应的重量列表为[2, 3, 4, 5],价值列表为[3, 4, 5, 6],背包容量为8。然后调用knapsack_dynamic_programming函数,将问题实例作为参数传入,得到最优解的总价值和被选择的物品列表,并通过print语句输出结果。

四、最长公共子串

4.1 最长公共子串

最长公共子串(Longest Common Substring)是一种常见的字符串匹配问题,用于寻找两个或多个字符串中最长的共同连续子串。

在最长公共子串问题中,给定两个字符串,我们要找到它们之间最长的连续子串,该子串在两个字符串中以相同的顺序出现。

例如,对于字符串"ABCD"和"BCDE",它们的最长公共子串是"BCD",因为这个子串在两个字符串中以相同的顺序出现,并且是最长的连续子串。

解决最长公共子串问题的一种常见方法是使用动态规划。动态规划的思想是将大问题拆分为小问题,并利用小问题的解来构建大问题的解。

基本思路是使用一个二维数组来存储中间结果,其中dp[i][j]表示以第一个字符串的第i个字符和第二个字符串的第j个字符结尾的最长公共子串的长度。

通过遍历两个字符串的所有字符,如果当前字符相等,则说明可以构建更长的公共子串,因此将dp[i][j]设置为dp[i-1][j-1] + 1。如果当前字符不相等,则说明无法构建连续的公共子串,将dp[i][j]设置为0。

在遍历的过程中,记录最长公共子串的长度和对应的结束索引,以便最后根据这些信息找到最长公共子串。

最终,根据最长公共子串的长度和结束索引,可以通过切片操作获取最长公共子串。

总结起来,最长公共子串问题可以通过动态规划算法来解决,其中通过构建二维数组记录中间结果,通过遍历两个字符串找到最长公共子串的长度和位置,最后根据这些信息得到最长公共子串。

实现的代码为:

def longest_common_substring(str1, str2):
    m = len(str1)
    n = len(str2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_length = 0
    end_index = 0

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > max_length:
                    max_length = dp[i][j]
                    end_index = i

    longest_substring = str1[end_index - max_length:end_index]
    return longest_substring


# 示例用法
str1 = "abcdefg"
str2 = "xyzabcd"
result = longest_common_substring(str1, str2)
print("Longest Common Substring:", result)

在该示例代码中,longest_common_substring函数接受两个字符串str1和str2作为输入,并返回它们的最长公共子串。

使用一个二维数组dp来存储中间结果,其中dp[i][j]表示以str1[i-1]和str2[j-1]结尾的最长公共子串的长度。通过遍历两个字符串,如果当前字符相等,则最长公共子串长度加1,并且更新最大长度和对应的结束索引。

最后,根据最大长度和结束索引,通过切片操作获取最长公共子串,并将其返回。

在示例用法中,给定字符串str1为"abcdefg",str2为"xyzabcd",调用longest_common_substring函数,输出最长公共子串"abcd"。

输出结果为:文章来源地址https://www.toymoban.com/news/detail-493368.html

Longest Common Substring: abcd

4.2 最长公共子序列

最长公共子序列(Longest Common Subsequence)是一种常见的字符串匹配问题,用于寻找两个或多个字符串中最长的共同子序列。

在最长公共子序列问题中,给定两个字符串,我们要找到它们之间最长的共同子序列,该子序列不要求在两个字符串中连续出现,只要保持相对顺序即可。

例如,对于字符串"ABCD"和"ACDF",它们的最长公共子序列是"ACD",因为这个子序列在两个字符串中以相同的顺序出现,并且是最长的。

解决最长公共子序列问题的一种常见方法是使用动态规划。动态规划的思想是将大问题拆分为小问题,并利用小问题的解来构建大问题的解。

基本思路是使用一个二维数组来存储中间结果,其中dp[i][j]表示第一个字符串的前i个字符和第二个字符串的前j个字符之间的最长公共子序列的长度。

通过遍历两个字符串的所有字符,如果当前字符相等,则说明可以构建更长的公共子序列,因此将dp[i][j]设置为dp[i-1][j-1] + 1。如果当前字符不相等,则说明无法构建公共子序列,需要在两个字符串中选择一个较长的子序列作为最长公共子序列,将dp[i][j]设置为max(dp[i-1][j], dp[i][j-1]),即继承上一个子问题的解。

在遍历的过程中,记录最长公共子序列的长度,以便最后获取最长公共子序列。

最终,根据二维数组dp中的结果,可以通过回溯或者递归来构建最长公共子序列。

总结起来,最长公共子序列问题可以通过动态规划算法来解决,其中通过构建二维数组记录中间结果,通过遍历两个字符串找到最长公共子序列的长度,最后根据中间结果构建最长公共子序列。

下面是一个使用动态规划算法求解最长公共子序列的Python示例代码:

def longest_common_subsequence(str1, str2):
    m = len(str1)
    n = len(str2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # 构造最长公共子序列
    i, j = m, n
    longest_subsequence = ""
    while i > 0 and j > 0:
        if str1[i - 1] == str2[j - 1]:
            longest_subsequence = str1[i - 1] + longest_subsequence
            i -= 1
            j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    return longest_subsequence


# 示例用法
str1 = "ABCD"
str2 = "ACDF"
result = longest_common_subsequence(str1, str2)
print("Longest Common Subsequence:", result)

在该示例代码中,longest_common_subsequence函数接受两个字符串str1和str2作为输入,并返回它们的最长公共子序列。

使用一个二维数组dp来存储中间结果,其中dp[i][j]表示第一个字符串的前i个字符和第二个字符串的前j个字符之间的最长公共子序列的长度。

通过遍历两个字符串的所有字符,如果当前字符相等,则最长公共子序列长度加1,即dp[i][j] = dp[i - 1][j - 1] + 1。如果当前字符不相等,则需要在两个字符串中选择一个较长的子序列作为最长公共子序列,即dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])。

在遍历的过程中,记录最长公共子序列的字符,以便最后构建最长公共子序列。通过回溯的方式,从dp数组的右下角开始,根据上一个状态的选择,逐步构建最长公共子序列。

最后,根据构建好的最长公共子序列,将其返回。

在示例用法中,给定字符串str1为"ABCD",str2为"ACDF",调用longest_common_subsequence函数,输出最长公共子序列"ACD"。

输出结果为:

Longest Common Subsequence: ACD

到了这里,关于【算法】算法学习七:动态规划 | 背包问题 | 最长公共子串(含源代码)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法设计与分析】(三)动态规划_更新中:斐波那契、二项式系数、树的最大独立集、最长递增、公共子序列、编辑距离、Hischberg、最优二叉搜索树、交替拿硬币、石子合并、背包、乘电梯

    分治 动态规划本篇 还差一堆 贪心 网络流 首先,怕误人子弟必须声明一下 本人很菜 (越复习越觉得完蛋了 作为一个科班研究生算法学成这样非常惭愧(跪 ,可能写的都不是很懂,很多内容打算背过去了。因为我发现好像真的有人看所以多提醒一句。。(大家就只食用目录

    2024年01月19日
    浏览(98)
  • day57|动态规划17-最长回文子串问题

    回文子串:强调连续 回文子序列:不强调连续 暴力思路:三层for循环 双指针思路: 动态规划 dp数组 dp[i][j]: 根据字符串的形式和所解决的问题确定dp数组的形式和含义。 递归公式 (分情况讨论) 2.1 如果 i j 2.2 如果 j-i 1 2.3 如果 j-i1: 此时依赖于dp[i+1][j-1]是不是一个回文子

    2024年02月09日
    浏览(39)
  • 【算法|动态规划No30】leetcode5. 最长回文子串

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月08日
    浏览(37)
  • (Java) 算法——动态规划 最长公共子序列 图解

    遇到了用动态规划来求解最长公共子序列问题,算法这块儿比较薄弱,便想着在网上找现成的思路和代码,也算拾人牙慧,但有一点没想到,都已经22年了,关于LCS问题网上给出的答案如此一言难尽……,只有零散几篇对于 新手 来说比较友好,但也仅仅这样,好在自己花了点

    2023年04月08日
    浏览(47)
  • 【动态规划】最长公共子序列——算法设计与分析

    子序列是给定序列中在任意位置去掉任意多个字符后得到的结果。例如: 给定序列 X X X : X : A B C B D A B X:ABCBDAB X : A BCB D A B X X X 的子序列: X 1 : A B C B D A B X_1:ABCBDAB X 1 ​ : A BCB D A B X 2 : A B C B X_2:ABCB X 2 ​ : A BCB X 3 : A C B B X_3:ACBB X 3 ​ : A CBB 给定两个序列

    2024年02月05日
    浏览(53)
  • 【算法题】动态规划中级阶段之最长回文子串、括号生成、跳跃游戏

    动态规划(Dynamic Programming,简称 DP)是一种解决多阶段决策过程最优化问题的方法。它是一种将复杂问题分解成重叠子问题的策略,通过维护每个子问题的最优解来推导出问题的最优解。 动态规划的主要思想是利用已求解的子问题的最优解来推导出更大问题的最优解,从而

    2024年02月12日
    浏览(43)
  • 动态规划-----最长公共子序列(及其衍生问题)

    目录 一.最长公共子序列的基本概念: 解决动态规划问题的一般思路(三大步骤): 二.最长公共子序列题目: 三.字符串的删除操作: 四.最小 ASCII 删除和: 首先需要科普一下,最长公共子序列(longest common sequence)和最长公共子串(longest common substring)不是一回事儿。什么

    2024年03月26日
    浏览(45)
  • 【算法】力扣【动态规划,LCS】1143. 最长公共子序列

    1143. 最长公共子序列 本文是对 LCS 这一 动态规划 模型的整理,以力扣平台上的算法题1143:最长公共子序列为模板题进行解析。 该题目要求计算两个字符串的最长公共子序列(Longest Common Subsequence,简称LCS)的长度。字符串的子序列是指在不改变字符顺序的情况下,通过删去

    2024年01月17日
    浏览(57)
  • 动态规划应用篇:详解最长公共子序列问题

    动态规划 是一个强大的工具,将复杂问题 分解 为多个容易解决的子问题,并且会对中间结果进行存储从而避免重复计算,然后将它们的解组合起来,形成大问题的解,高效地得出 全局最优解 。前面我们已经了解了动态规划的基础知识及一维动态规划问题的求解,今天,我

    2024年04月15日
    浏览(44)
  • 算法学习17-动态规划01:背包问题

    提示:以下是本篇文章正文内容: 提示:这里对文章进行总结: 💕💕💕

    2024年04月27日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包