Python贪心算法

105260 阅读 0 评论 0 点赞

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

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

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()

输出结果为：

请输入每种零钱的数量：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()

输出结果为：

这道题我们首先要判断当油量是满的时候是否可以大于所有相邻加油站之间的距离，然后开始迭代，使用while语句，如果i等于5的时候就退出循环，循环中当局部和大于n时就把局部和更新为当前距离，然后次数加一，直到退出循环。