python——三道贪心算法例题

约定不等于承诺〃 2022-06-06 00:08 169阅读 0赞

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

# -*- coding:utf-8 -*-
    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()

2.求最大子数组之和问题：给定一个整数数组（数组元素有负有正），求其连续子数组之和的最大值。

# -*- coding:utf-8 -*-
    def main():
        s = [12,-4,32,-36,12,6,-6]
        print("定义的数组为：",s)
        s_max, s_sum = 0, 0
        for i in range(len(s)):
            s_sum += s[i]
            if s_sum >= s_max:
                s_max = s_sum # 不断更新迭代s_max的值，尽可能的令其最大
            elif s_sum < 0:
                s_sum = 0
        print("最大子数组和为：",s_max)
    
    if __name__ == "__main__":
        main()

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

# 设汽车加满油后可行驶n公里，且旅途中有k个加油站
    
    def greedy():
        n = 100
        k = 5
        d = [50,80,39,60,40,32]
        # 表示加油站之间的距离
        num = 0
        # 表示加油次数
        for i in range(k):
            if d[i] > n:
                print('no solution')
                # 如果距离中得到任何一个数值大于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__':
        greedy()