原理

动态规划（Dynamic Programming，简称DP）是一种在数学、计算机科学和经济学中用于解决复杂问题的算法设计技术。它主要用于优化问题，特别是那些可以分解为更小的子问题，并且这些子问题存在重叠的情况。动态规划的核心思想是将一个大问题分解成若干个较小的问题，通过保存已经解决的子问题的答案，避免重复计算，从而提高效率。

动态规划通常适用于满足以下两个性质的问题：

  1. 最优子结构：如果一个问题的最优解包含了其子问题的最优解，则称这个问题具有最优子结构性质。
  2. 重叠子问题：在求解过程中，相同的子问题会被多次遇到和求解，即子问题之间存在重叠。

动态规划解决问题的一般步骤如下：

  • 定义状态：确定描述问题的状态变量，这通常是问题中的关键参数或指标。
  • 状态转移方程：根据问题的性质，找到从一个状态转移到另一个状态的关系式。
  • 边界条件：定义最简单情况下的解，作为递归的基础。
  • 计算顺序：确定如何依次计算各个状态的值，确保在计算某个状态时，所有需要的子状态都已经计算完毕。
  • 结果构造：最后，根据所得到的状态值构造出问题的解。

动态规划有两种主要的实现方法：

  • 自底向上法（Bottom-Up）：从最简单的子问题开始逐步构建到最终问题的解，通常使用迭代的方式。
  • 自顶向下法（Top-Down）：从原始问题出发，将问题分解为子问题，通过记忆化（Memoization）技术存储已经解决的子问题的结果，以避免重复计算，通常使用递归的方式。

动态规划的一个经典例子是斐波那契数列的计算，其中每个数都是前两个数的和。其他常见的应用还包括背包问题、最短路径问题、编辑距离等。动态规划广泛应用于运筹学、控制理论、信息论、统计物理学等领域。

代码

凑硬币

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def coinChange(n):
    """
    用于计算找零的最少硬币数。
    参数n：要找零的金额
    返回值：最少硬币数量，如果无法找零，则返回-1
    """
    dp = [float('inf')] * (n + 1)  # 初始化动态规划数组
    dp[0] = 0  # 找零金额为 0 时，需要 0 枚硬币
    for i in range(1, n + 1):
        if i >= 2:
            dp[i] = min(dp[i], dp[i - 2] + 1)
        if i >= 5:
            dp[i] = min(dp[i], dp[i - 5] + 1)
        if i >= 7:
            dp[i] = min(dp[i], dp[i - 7] + 1)
    if dp[n] != float('inf'):
        return dp[n]
    else:
        return -1
n=int(input('请输入要拼的金额：'))
res=coinChange(n)
print(res)

# # 递归算法
# def f(x):
#     """
#     递归函数，用于计算找零的最少硬币数。
#     参数x：找零的金额
#     返回值：最少硬币数量，如果无法找零，则返回无穷大
#     """
#     if x == 0:
#         return 0  # 如果找零金额为 0，则不需要任何硬币，直接返回 0
#     res = float('inf')  # 用一个很大的数表示无穷大，用于比较最小值
#     if x >= 2:
#         # 如果找零金额大于等于 2 元，尝试使用一枚 2 元硬币
#         res = min(f(x - 2) + 1, res)  # 递归调用 f 函数，并加上这一枚硬币
#     if x >= 5:
#         # 如果找零金额大于等于 5 元，尝试使用一枚 5 元硬币
#         res = min(f(x - 5) + 1, res)  # 递归调用 f 函数，并加上这一枚硬币
#     if x >= 7:
#         # 如果找零金额大于等于 7 元，尝试使用一枚 7 元硬币
#         res = min(f(x - 7) + 1, res)  # 递归调用 f 函数，并加上这一枚硬币
#     return res  # 返回最少硬币数量，如果无法找零，则返回无穷大
# n=int(input('请输入要拼的金额：'))
# res=f(n)
# print(res)

背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def knapsack(weights, values, capacity):
    """
    用于求解0-1背包问题的最大价值
    参数weights：物品的重量列表
    参数values：物品的价值列表
    参数capacity：背包的容量
    返回值：最大价值
    """
    n = len(weights)  # 物品数量
    dp = [[0 for j in range(capacity + 1)] for i in range(n + 1)]  # 初始化动态规划数组

    # 动态规划求解过程
    for i in range(1, n + 1): # 范围为1~n，括号左闭右开
        for j in range(1, capacity + 1):
            if j < weights[i - 1]:  # 背包容量小于当前物品重量，不能选择当前物品
                dp[i][j] = dp[i - 1][j]
            else:  # 能选择当前物品，要选择价值更大的方案
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
    return dp[n][capacity]
w = input('请输入物品的重量列表，用逗号分隔：')
v = input('请输入物品的价值列表，用逗号分隔：')
c = int(input('请输入背包的容量：'))
weights = [int(x) for x in w.split(',')]  # 将输入的字符串转换为整数列表
values = [int(x) for x in v.split(',')]
res = knapsack(weights, values, c)
print('最大价值为:', res)