赞
踩
动态规划(Dynamic Programming,简称 DP)是一种在数学、计算机科学和经济学中使用的,通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。
动态规划的工作原理基于两个核心概念:
动态规划通常包含以下步骤:
动态规划的实现方式通常包括自底向上和带备忘录的自顶向下两种。
动态规划在许多领域都有广泛的应用,包括背包问题、最短路径问题、最长公共子序列问题、编辑距离问题、资源分配问题等。
以经典的0-1背包问题为例,下面是使用动态规划求解0-1背包问题的Python代码:
python复制代码
def knapsack(values, weights, capacity): | |
n = len(values) | |
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)] | |
for i in range(1, n + 1): | |
for w in range(1, capacity + 1): | |
if weights[i - 1] <= w: | |
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]) | |
else: | |
dp[i][w] = dp[i - 1][w] | |
return dp[n][capacity] | |
# 示例 | |
values = [60, 100, 120] | |
weights = [10, 20, 30] | |
capacity = 50 | |
print(knapsack(values, weights, capacity)) # 输出:220 |
在这个例子中,values
数组表示每个物品的价值,weights
数组表示每个物品的重量,capacity
表示背包的容量。dp[i][w]
表示考虑前i
个物品,在背包容量为w
的情况下能够得到的最大价值。通过填充这个二维数组,我们可以得到原问题的解。
带备忘录的自底向上方法结合了自底向上和递归两种策略。它首先通过递归地求解子问题来构建问题的解空间,但为了避免重复计算,它使用一个“备忘录”或称为“查找表”来存储已经计算过的子问题的解。这样,当再次遇到相同的子问题时,可以直接从备忘录中查找结果,而不是重新计算。
这种方法的优势在于它结合了递归的清晰性和自底向上的效率。递归使得代码更易于理解和编写,而备忘录则确保了计算的高效性,避免了不必要的重复工作。
下面是一个使用带备忘录的自底向上方法解决0-1背包问题的Python代码实例:
python复制代码
def knapsack_memoization(values, weights, capacity): | |
memo = [[None] * (capacity + 1) for _ in range(len(values) + 1)] | |
def dp(i, w): | |
# 如果当前子问题的解已经在备忘录中,则直接返回 | |
if memo[i][w] is not None: | |
return memo[i][w] | |
# 递归的基本情况 | |
if i == 0 or w == 0: | |
return 0 | |
# 如果当前物品重量大于背包容量,则不考虑该物品 | |
if weights[i - 1] > w: | |
memo[i][w] = dp(i - 1, w) | |
else: | |
# 否则,考虑选择当前物品或不选择当前物品两种情况中的较大值 | |
memo[i][w] = max(dp(i - 1, w), values[i - 1] + dp(i - 1, w - weights[i - 1])) | |
return memo[i][w] | |
# 调用递归函数,求解原问题 | |
return dp(len(values), capacity) | |
# 示例 | |
values = [60, 100, 120] | |
weights = [10, 20, 30] | |
capacity = 50 | |
print(knapsack_memoization(values, weights, capacity)) # 输出:220 |
在这个例子中,memo
数组就是我们的备忘录,用于存储子问题的解。dp
函数是一个递归函数,它首先检查备忘录中是否已经存在当前子问题的解。如果存在,则直接返回该解;如果不存在,则递归地计算子问题的解,并将结果存储在备忘录中。这样,当相同的子问题再次被调用时,就可以直接从备忘录中取得结果,避免重复计算。
注意,虽然这种方法在概念上使用了递归,但实际上它是通过自底向上的方式填充备忘录的,因此避免了递归的深度限制,并且在实际执行时通常比纯递归方法更高效。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。