Python贪心算法详解

2024-11-08 4

贪心算法也被称为贪婪算法，它是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

1. 贪心算法基础

贪心算法的解题方式是从可选的第一个解开始逐步到达目标解，如果在寻解的过程

中因某种条件限制而停止向前，就得到一个近似解，因此贪心算法存在以下几个问题：

1) 贪心算法得到的解不一定是最优解

2) 不适用于最值问题

3) 适用于部分约束条件的问题求解

贪心算法的过程如下：

1．建立数学模型来描述问题

2．把求解的问题分成若干个子问题

3．对每一子问题求解，得到子问题的局部最优解

4．把子问题的解局部最优解合成原来解问题的一个解

算法求解过程是首先从某一解向目标值出发，得到可行解的元素，然后合成所有解元素而得到一个可行解。

2. 找零问题

1) 问题描述

假设只有1 分、2 分、五分、1角、二角、五角、1元的硬币。在超市结账时，如果需要找零钱，收银员希望将最少的硬币数找给顾客。那么，给定需要找的零钱数目，如何求得最少的硬币数呢？

2) 问题分析

在找零的时候会有多种方案，当零钱为五角的时候，可以用一个五角的，也可以用两个两角的和一个一角的，还可以用五个一角的，还可以用一个两角的和三个一角的，因此在我们在求解这个问题的时候可以从这些角度来思考。

3) 代码实现

  def main():
    d = [0.01,0.02,0.05,0.1,0.2,0.5,1.0] # 存储每种硬币面值
    d_num = [] # 存储每种硬币的数量
    s = 0
    # 拥有的零钱总和
    temp = input('请输入每种零钱的数量：')
    d_num0 = temp.split(" ")
    for i in range(0, len(d_num0)):
        d_num.append(int(d_num0[i]))
        s += d[i] * d_num[i] # 计算出收银员拥有多少钱
    sum = float(input("请输入需要找的零钱:"))
    if sum > s:
        # 当输入的总金额比收银员的总金额多时，无法进行找零
        print("数据有错")
        return 0
    s = s - sum
    # 要想用的钱币数量最少，那么需要利用所有面值大的钱币，因此从数组的面值大的元素开始遍历
    i = 6
    while i >= 0: 
        if sum >= d[i]:
            n = int(sum / d[i])
            if n >= d_num[i]:
                n = d_num[i]  # 更新n
            sum -= n * d[i] # 贪心的关键步骤，使sum动态的改变
            print("用了%d个%f元硬币"%(n, d[i]))
        i -= 1
if __name__ == "__main__":
main()

输出结果为：

1

2

3

4

5

请输入每种零钱的数量：14 12 13 13 23 13 6
请输入需要找的零钱:1.3
用了1个1.000000元硬币
用了1个0.200000元硬币
用了1个0.100000元硬币

首先输入了所有零钱的数量，然后计算出钱的总数，保证零钱能够找零，然后进入下一步找零。为了保证找零的数量最小，使用大面值的硬币，因此从大面值的硬币开始遍历，如果大面值无法满足的时候再往下取，这个算法的关键就在于sum的值是动态改变的，根据改变后的sum值再去进行判断，直到最后完成。

3. 汽车加油问题

一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。对于给定的n(n <= 5000)和k(k <= 1000)个加油站位置，编程计算最少加油次数。

代码如下：

 def petrol():
    n = 100
    k = 5
    d = [23,45,39,70,54,62]
    # 表示加油站之间的距离
    num = 0
    # 表示加油次数
    for i in range(k):
        if d[i] > n:
            print('没有适合的')
            # 如果距离中得到任何一个数值大于n 则无法计算
            return 
    i, s = 0, 0
    # 利用s进行迭代
    while i <= k:
        s += d[i]
        if s >= n:
            # 当局部和大于n时则局部和更新为当前距离
            s = d[i]
            # 贪心意在令每一次加满油之后跑尽可能多的距离
            num += 1
        i += 1
    print(num)
if __name__ == '__main__':
    petrol()