使用python解决硬币找零问题

这段 Python 代码主要解决了经典的硬币找零问题，并对求解过程进行可视化展示。硬币找零问题是指，给定不同面额的硬币 coins 和一个总金额 amount，需要找出能够凑成总金额所需的最少硬币数量，如果无法凑成则返回 -1。代码中定义了两个主要函数，一个用于计算最少硬币数量，另一个用于将计算结果进行可视化。

代码详细说明

1. 导入库

收起

python

import matplotlib.pyplot as plt

这行代码导入了 matplotlib 库中的 pyplot 模块，并将其重命名为 plt。matplotlib 是一个强大的 Python 绘图库，pyplot 模块提供了类似于 MATLAB 的绘图接口，用于创建各种类型的图表，这里主要用于绘制硬币找零问题的可视化结果。

2. coinChange 函数

收起

python

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

• 功能：该函数使用动态规划（Dynamic Programming）的方法来计算凑成目标金额 amount 所需的最少硬币数量。
• 参数：
  • coins：一个列表，包含了不同面额的硬币。
  • amount：一个整数，表示需要凑成的目标金额。
• 返回值：一个整数，如果能够凑成目标金额，返回所需的最少硬币数量；如果无法凑成，返回 -1。
• 实现步骤：
  1. 初始化动态规划数组 dp：dp 数组的长度为 amount + 1，初始值都设为正无穷大 float('inf')。dp[i] 表示凑成金额 i 所需的最少硬币数量。将 dp[0] 设为 0，因为凑成金额 0 不需要任何硬币。
  2. 双重循环填充 dp 数组：
     • 外层循环遍历从 1 到 amount 的每个金额 i。
     • 内层循环遍历每种硬币面额 coin，如果当前硬币面额 coin 小于等于当前金额 i，则更新 dp[i] 的值为 dp[i] 和 dp[i - coin] + 1 中的较小值。这里的 dp[i - coin] + 1 表示使用当前硬币 coin 后，凑成金额 i 所需的最少硬币数量。
  3. 返回结果：如果 dp[amount] 仍然是正无穷大，说明无法凑成目标金额，返回 -1；否则返回 dp[amount]。

3. plot_coin_change 函数

收起

python

def plot_coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    # 绘制结果
    x = list(range(amount + 1))  # x轴：金额
    y = dp  # y轴：所需最小硬币数

    plt.plot(x, y, marker='o', linestyle='-', color='b', label='Minimum Coins')
    plt.title('Coin Change Problem Visualization')
    plt.xlabel('Amount')
    plt.ylabel('Minimum Number of Coins')
    plt.grid(True)
    plt.legend()
    plt.show()

• 功能：该函数用于计算凑成不同金额所需的最少硬币数量，并将结果进行可视化展示。
• 参数：
  • coins：一个列表，包含了不同面额的硬币。
  • amount：一个整数，表示需要考虑的最大金额。
• 返回值：无，该函数会直接显示绘制好的图表。
• 实现步骤：
  1. 计算最少硬币数量：与 coinChange 函数的前半部分逻辑相同，使用动态规划方法计算凑成从 0 到 amount 每个金额所需的最少硬币数量，并存储在 dp 数组中。
  2. 准备绘图数据：
     • x 轴数据：x 是一个列表，包含从 0 到 amount 的所有整数，表示不同的金额。
     • y 轴数据：y 就是 dp 数组，其中每个元素表示凑成对应金额所需的最少硬币数量。
  3. 绘制图表：
     • 使用 plt.plot 函数绘制折线图，设置标记点为圆形 marker='o'，线条样式为实线 linestyle='-'，颜色为蓝色 color='b'，并添加图例标签 label='Minimum Coins'。
     • 使用 plt.title 函数设置图表的标题为 'Coin Change Problem Visualization'。
     • 使用 plt.xlabel 和 plt.ylabel 函数分别设置 x 轴和 y 轴的标签。
     • 使用 plt.grid(True) 函数开启网格线，方便观察数据。
     • 使用 plt.legend() 函数显示图例。
     • 最后使用 plt.show() 函数显示绘制好的图表。

4. 示例调用

收起

python

# 示例：硬币面值为 [1, 2, 5]，目标金额为 11
coins = [1, 2, 5]
amount = 11
plot_coin_change(coins, amount)

这里定义了硬币面额列表 coins 为 [1, 2, 5]，目标金额 amount 为 11，并调用 plot_coin_change 函数对该硬币找零问题的求解结果进行可视化展示。

总结

这段代码通过动态规划的方法高效地解决了硬币找零问题，并利用 matplotlib 库将求解过程进行可视化，帮助用户更直观地理解不同金额下所需的最少硬币数量。

完整代码

import matplotlib.pyplot as plt

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

def plot_coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    # 绘制结果
    x = list(range(amount + 1))  # x轴：金额
    y = dp  # y轴：所需最小硬币数

    plt.plot(x, y, marker='o', linestyle='-', color='b', label='Minimum Coins')
    plt.title('Coin Change Problem Visualization')
    plt.xlabel('Amount')
    plt.ylabel('Minimum Number of Coins')
    plt.grid(True)
    plt.legend()
    plt.show()

# 示例：硬币面值为 [1, 2, 5]，目标金额为 11
coins = [1, 2, 5]
amount = 11
plot_coin_change(coins, amount)