ITPub博客
首页 博客 专栏 学院 社区 IT新媒体评选
发博

首页 > 应用开发 > Python > Python 中如何实现动态规划？

Python 中如何实现动态规划？

原创 Python 作者：mingtian66 时间：2024-11-12 12:22:27 0 删除 编辑

在 Python 中实现动态规划（Dynamic Programming, DP）可以用来解决许多具有重叠子问题和最优子结构性质的问题。动态规划的核心是通过存储子问题的解，避免重复计算，从而降低时间复杂度。
1. 动态规划的基本步骤

实现动态规划通常需要以下步骤：

    定义状态：明确问题的子问题，定义状态表示子问题的解。
    状态转移方程：找到当前状态和之前状态的关系，构建递推关系。
    初始化：初始化基础状态的解。
    结果提取：根据状态转移方程，逐步计算到目标状态的解，得到最终解。

2. 动态规划的实现方法

动态规划通常有两种实现方式：

    自顶向下（备忘录法）：使用递归和备忘录数组存储子问题的解，避免重复计算。
    自底向上（迭代法）：从基础状态开始，通过迭代逐步计算到最终结果。

例子：斐波那契数列

假设要计算第 n 个斐波那契数列，满足递推关系 F(n) = F(n-1) + F(n-2)，且 F(0) = 0，F(1) = 1。
方法 1：自顶向下（备忘录法）

def fibonacci_memo(n, memo={}):
    # 基础情况
    if n <= 1:
        return n
    # 如果结果已在备忘录中，直接返回
    if n in memo:
        return memo[n]
    # 否则，递归计算并存储结果到备忘录中
    memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    return memo[n]

# 示例调用
n = 10
print(f"第 {n} 个斐波那契数是: {fibonacci_memo(n)}")

方法 2：自底向上（迭代法）

def fibonacci_dp(n):
    if n <= 1:
        return n
    # 初始化基础状态
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    # 根据状态转移方程迭代填充表
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

# 示例调用
print(f"第 {n} 个斐波那契数是: {fibonacci_dp(n)}")

3. 例子：背包问题

假设有一个 0/1 背包问题，有 n 个物品，每个物品有一个重量 w[i] 和价值 v[i]，背包的最大承重是 W，要求在不超过承重的前提下，使得背包中的总价值最大化。
自底向上动态规划

def knapsack(values, weights, W):
    n = len(values)
    # 初始化 DP 表，dp[i][j] 表示前 i 个物品在容量 j 下的最大价值
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    # 填表
    for i in range(1, n + 1):
        for j in range(W + 1):
            if weights[i-1] <= j:
                # 不选当前物品或选当前物品，取最大值
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - weights[i-1]] + values[i-1])
            else:
                # 无法选当前物品
                dp[i][j] = dp[i-1][j]

    # 返回最后一项，即所有物品在容量 W 下的最大值
    return dp[n][W]

# 示例调用
values = [60, 100, 120]
weights = [10, 20, 30]
W = 50
print("背包问题的最大价值是:", knapsack(values, weights, W))

总结

    备忘录法适用于递归，较直观，但栈深可能受限。
    迭代法从基础状态逐步推算，通常效率更高。

来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/70040412/viewspace-3048462/ ，如需转载，请注明出处，否则将追究法律责任。

0
0
上一篇： python中如何实现 A* 算法求最短路径？
下一篇： Java 中的异常链是什么？
请登录后发表评论 登录
全部评论
mingtian66

注册时间：2024-08-07

  • 博文量
    589
  • 访问量
    602978

最新文章

支持我们 作者招募 用户协议 FAQ Contact Us

北京盛拓优讯信息技术有限公司. 版权所有  京ICP备16024965号-8 北京市公安局海淀分局网监中心备案编号：11010802021510 niuxiaotong@pcpop.com 17352615567 未成年人举报专区

广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员

违法和不良信息举报电话:18101376593