贪心算法的Python实现方法

Question

问题遇到的现象和发生背景

题目名称：硬币的面值
时间限制：1000ms内存限制：256M
题目描述
小A有n枚硬币，现在要买一样不超过m元的商品，他不想被找零，同时又不想带太多的硬币，且硬币可以重复，现在已知这n枚硬币的价值，请问最少需要多少硬币就能组合成所有可能的价格？

遇到的现象和发生背景，请写出第一个错误信息

参考CSDN- 请叫我问哥解答：https://blog.csdn.net/soonway2010/article/details/128237725
该解答带入答题环境，样本测试后的通过率为90%，已对代码进行了标注，没发现算法的明显问题，但就是调试不过去。

用代码块功能插入代码，请勿粘贴截图。 不用代码块回答率下降 50%

#map函数的第一个参数是一个函数，第二个参数是一个序列，里面的每个元素作为函数的参数进行计算和判断。函数返回值则被作为新的元素存储起来。
n, m = map(int, input().split())
## 使用 list() 将map转换为列表
value = list(map(int, input().split()))
value.sort()
#value=sorted(value)
if value[0] != 1: #如果没有面值为1的硬币，则必定不符合条件
    print("No answer!!!")
elif n == 1: #如果只有一种面值（也就是1），则只能取m枚硬币
    print(m)
else:
    res = maxvalue = value[1] - 1 #由于有两种或更多面值，所以初始至少需要第二种面值为（value[1] - 1）的硬币
    i = 1
    while True:
        while i < n and maxvalue+1 >= value[i]: #找到现有硬币可以组成最大金额的边界值
            i += 1
        if i == n: #如果已经是最后一种面值，就没必要再累加了，直接用还差多少钱除以最大面值，向上取整
            d = m - maxvalue
            res += d//value[i-1] + bool(d%value[i-1])
            print(res)
            break
        else: #计算现有硬币可以组成的最大金额，如果已经大于等于m，则结束计算
            maxvalue += value[i-1]
            res += 1
            if maxvalue >= m:
                print(res)
                break

运行结果及详细报错内容

我的解答思路和尝试过的方法，不写自己思路的，回答率下降 60%

对该算法的理解标注在代码段中了。

我想要达到的结果，如果你需要快速回答，请尝试 “付费悬赏”

利用Python语言，编写代码，通过答题样本测试，达到100%。

Answer 1

在硬币的面值问题中，我们可以使用贪心算法来求解。具体方法如下：

• 1.将硬币按价值从大到小排序。
• 2.依次将最大的硬币加入组合中，直到组合的价值大于等于目标价值。

下面是Python代码实现：

# 面值列表
coins = [1, 2, 5, 10, 20, 50, 100]

# 目标价值
m = 134

# 初始化组合价值为0
combination_value = 0

# 初始化硬币数量为0
coin_count = 0

# 从大到小遍历硬币
for coin in reversed(coins):
    # 如果当前硬币的价值小于目标价值，则将当前硬币加入组合
    while combination_value + coin <= m:
        combination_value += coin
        coin_count += 1

# 输出最少硬币数量
print(coin_count)

运行结果为：

9

关于贪心算法的时间复杂度，在这道题目中，我们只需要遍历一次硬币列表，因此时间复杂度是O(n)，其中n是硬币的数量。