Python动态规划

动态规划（Dynamic Programming，简称DP）是解决多阶段决策过程最优化问题的一种方法。

动态规划算法的基本思想是:
将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；
对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。
动态规划算法将问题的解决方案视为一系列决策的结果

1.斐波那契数列

斐波那契数列公式为: $F(n)=F(n−1)+F(n−2)$
初始化第1项和第2项为1
求该数列第n项

递归解法

class Solution:
    def Fibonacci(self, n: int) -> int:
        if n <= 2:
            return 1
        else:
            return self.Fibonacci(n - 1) + self.Fibonacci(n - 2)

遍历解法

class Solution:
    def Fibonacci(self, n: int) -> int:
        if n <= 2:
            return 1
        else:
            a, b = 1, 1
            for _ in range(2, n):
                a, b = b, a + b
            return b

动态规划解法

• 定义状态: 定义状态dp[i]，表示斐波那契数列的第 i 项的值
• 状态转移方程: 根据斐波那契数列的定义，可以得到状态转移方程: dp[i] = dp[i - 1] + dp[i - 2]
• 边界条件: 初始条件为dp[0] = 0和dp[1] = 1

class Solution:
    def Fibonacci(self, n: int) -> int:
        if n <= 2:
            return 1
        dp = [0 for i in range(n + 1)]
        dp[1] = 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

2. 0/1背包问题

给定一个容量为 M 的背包，以及 n 个物品，每个物品有一个重量 w[i] 和一个价值 c[i] 。要求在不超过背包容量的前提下，选择物品使得总价值最大。

【输入】
第1行: 两个整数，M表示背包容量，n表示物品数量。
第2~n+1行: 每行两个整数wi、ci，表示每个物品的重量和价值。
【输入样例】

10 4
2 1
3 3
4 5
7 9

构建动态规划表

假设有以下物品和背包容量:

背包容量 M = 10

填充动态规划表来计算最大价值:

最终，dp[4][10] = 12，表示在不超过重量 10 的情况下，能获得的最大价值为 12

• 定义状态: dp[i][j] 表示前i个物品中，背包最大载重为j的情况下，最大价值的总和
• 状态转移方程:
  如果不选择第i个物品 dp[i][j]=dp[i - 1][j]
  如果选择第i个物品 dp[i][j]=dp[i - 1][j - w[i]] + c[i]
  可得 $dp[i][j] = \max(dp[i-1][j], dp[i-1][j - w[i]] + c[i])$
• 边界条件:
  dp[0][j] = 0 （没有物品时，最大价值为 0）
  dp[i][0] = 0 （背包容量为 0 时，最大价值为 0）

代码实现

# 读取背包容量 M 和物品数量 n
M, n = map(int, input().split())

# 初始化物品重量和价值数组，长度为 n+1，初始值为0
w = [0] * (n + 1)
c = [0] * (n + 1)

# 读取每个物品的重量和价值
for i in range(1, n + 1):
    w[i], c[i] = map(int, input().split())

# 初始化 dp 数组，dp[i][j] 表示前 i 个物品在容量为 j 时的最大价值
dp = [[0 for _ in range(M + 1)] for _ in range(n + 1)]

# 动态规划求解
for i in range(1, n + 1):  # 遍历每个物品
    for j in range(1, M + 1):  # 遍历每个容量
        if j < w[i]:  # 当前容量不够放下第 i 个物品
            dp[i][j] = dp[i - 1][j]
        else:  # 当前容量可以放下第 i 个物品，取最大值
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i])

# 查看动态规划表
for i in range(n + 1):
    for j in range(M + 1):
        print(dp[i][j], end=" ")
    print()

# 输出最大价值
print(dp[n][M])

参考资料：

1. https://blog.csdn.net/qq_37756660/article/details/137475180
2. 听懂不翻车系列之--背包问题