python算法学习:贪心算法

2022-08-0710:26:35数据结构与算法Comments1,044 views字数 2413阅读模式

贪心算法也被称为贪婪算法,它是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

1. 贪心算法基础文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

贪心算法的解题方式是从可选的第一个解开始逐步到达目标解,如果在寻解的过程文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

中因某种条件限制而停止向前,就得到一个近似解,因此贪心算法存在以下几个问题:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

1) 贪心算法得到的解不一定是最优解文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

2) 不适用于最值问题文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

3) 适用于部分约束条件的问题求解文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

贪心算法的过程如下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

1.建立数学模型来描述问题文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

2.把求解的问题分成若干个子问题文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

3.对每一子问题求解,得到子问题的局部最优解文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

4.把子问题的解局部最优解合成原来解问题的一个解文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

算法求解过程是首先从某一解向目标值出发,得到可行解的元素,然后合成所有解元素而得到一个可行解。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

 2. 找零问题文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

1) 问题描述:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

假设只有1 分、2 分、五分、1角、二角、五角、1元的硬币。在超市结账时,如果需要找零钱,收银员希望将最少的硬币数找给顾客。那么,给定需要找的零钱数目,如何求得最少的硬币数呢?文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

2) 问题分析文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

在找零的时候会有多种方案,当零钱为五角的时候,可以用一个五角的,也可以用文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

两个两角的和一个一角的,还可以用五个一角的,还可以用一个两角的和三个一角的, 因此在我们在求解这个问题的时候可以从这些角度来思考。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

3) 代码实现文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

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

输出结果为:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

1
2
3
4
5
请输入每种零钱的数量:14 12 13 13 23 13 6
请输入需要找的零钱:1.3
用了11.000000元硬币
用了10.200000元硬币
用了10.100000元硬币

首先输入了所有零钱的数量,然后计算出钱的总数,保证零钱能够找零,然后进入下一步找零。为了保证找零的数量最小,使用大面值的硬币,因此从大面值的硬币开始遍历,如果大面值无法满足的时候再往下取,这个算法的关键就在于sum的值是动态改变的,根据改变后的sum值再去进行判断,直到最后完成。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

 3. 汽车加油问题文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法,指出应在哪些加油站停靠加油,使沿途加油次数最少。 对于给定的n(n <= 5000)和k(k <= 1000)个加油站位置,编程计算最少加油次数。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

代码如下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

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

输出结果为文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

1
4

这道题我们首先要判断当油量是满的时候是否可以大于所有相邻加油站之间的距离,然后开始迭代,使用while语句,如果i等于5的时候就退出循环,循环中当局部和大于n时就把局部和更新为当前距离,然后次数加一,直到退出循环。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26688.html

  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/26688.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定