动态规划（Dynamic Programming）详解

创作时间:

作者:

@小白创作中心

动态规划（Dynamic Programming）详解

引用

CSDN

https://blog.csdn.net/ZuoZuoDuiChang/article/details/137448759

动态规划（Dynamic Programming）是一种重要的算法设计方法，适用于解决具有最优子结构和重叠子问题性质的问题。本文将详细介绍动态规划的基本原理，并通过一个经典的问题——背包问题，来演示动态规划的具体应用。

动态规划的基本原理

动态规划解决问题的一般步骤包括：

定义状态：确定问题的状态，通常以一维、二维数组等形式表示，其中状态表示了问题的不同维度的变化情况。
确定状态转移方程：建立状态之间的转移关系，即如何从一个状态转移到下一个状态。这一步是动态规划问题的核心。
确定初始条件：确定问题中的边界条件，即初始状态的值。
计算顺序：确定状态之间的计算顺序，通常采用自底向上的方式。

背包问题（0/1 Knapsack Problem）

背包问题是动态规划的一个经典应用场景，描述为：给定一个背包，它能承载一定重量的物品，并有一系列待放入的物品，每个物品都有自己的重量和价值。要求在不超过背包承载重量的情况下，选择一些物品放入背包，使得背包中物品的总价值最大。

问题建模

假设有n nn个物品，背包的承重为W WW，第i ii个物品的重量为w e i g h t [ i ] weight[i]weight[i]，价值为v a l u e [ i ] value[i]value[i]。我们用d p [ i ] [ j ] dp[i][j]dp[i][j]表示考虑前i ii个物品，背包容量为j jj时的最大价值。

状态转移方程

根据背包问题的性质，我们可以得到状态转移方程：

d p [ i ] [ j ] = max ⁡ ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w e i g h t [ i ] ] + v a l u e [ i ] ) dp[i][j] = \max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])dp[i][j]=max(dp[i−1][j],dp[i−1][j−weight[i]]+value[i])

Python实现

def knapsack(weights, values, W, n):
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(1, 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]
    
    return dp[n][W]

# 示例
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
W = 5
n = len(weights)
print("背包问题的最大价值为：", knapsack(weights, values, W, n))  # 输出：9