核心算法6贪心算法(代码片段)

关键词：

贪心算法就是遵循某种既定原则，不断地选取当前条件下最优的选择来构造每一个子步骤的解决方案，直到获得问题最终的求解。在对问题求解时，总是做出在当前看最好的选择。

也就是说，不从整体最优上考虑，所做的仅是在某种意义上的局部最优解。

利用贪心算法解题，需要解决两个问题

1. 问题是否适合用贪心算法求解

   所求问题是否具有贪心选择性质
   贪心选择性质：是指应用同一种规则F，将原问题变为一个相似但规模更小的子问题，后面的每一步都是当前看来最佳的选择。这种选择依赖于已作出的选择，但不依赖与未作出的选择。从全局看，运用贪心策略解决的问题在程序的运行过程中无回溯过程。
   

2. 问题是否具有局部最优解

   问题具有局部最优解，从而选择一个贪心标准，得到问题的最优解
   解题思路：
   1. 建立对问题精确描述的数学模型，包括定义最优解的模型
   2. 将问题分成一系列子问题，同时定义子问题的最优解结构
   3. 应用贪心算法可以确定每个子问题局部最优，并根据最优模型，用子问题的局部最优解堆叠出全局最优解
   

• 硬币找零问题
• 活动安排问题
• 哈夫曼编码

硬币找零问题

问题描述

用最少硬币支付指定额度问题

假设，有6重不同面值的硬币，各硬币的面值分别为5分，1角，2角，5角，1元，2元。现要用这些面值的硬币来购物和找钱。购物时规定了可以使用的各种面值的硬币个数。假定商店里面各面值的硬币足够多，顾客也可以用多种方式支付。在一次购物中，希望使用最少硬币个数

举例，一名顾客需要付款0.55元，但顾客没有5角的硬币

1. 第一种情况

   付款：0.2 + 0.2 + 0.1 + 0.05 = 0.55

   找零：0

2. 第二种情况

   付款：1

   找零：0.2 + 0.2 + 0.05

3. 第三种情况

   付款：1 + 0.05

   找零：0.5

那么，问题来了，对于给定的各种面值的硬币个数和付款金额，如何计算使用硬币个数最少的交易方案。

其核心思想为消费者硬币数量有限，商店的硬币数量无限，用公式描述：

• MIN(消费者支付硬币个数 + 商店找零硬币个数)
• 支付值 - 找零值 = 商品值

则问题转换为寻找上面两个问题的最优解，其贪心算法为：

? MAX(消费者拥有的硬币面值 - 商店拥有的硬币面值) 优先使用

假如，消费者拥有2元的硬币，商店拥有5分的硬币，因此MAX ：2元 - 5分 = 195分

组合所有情况：

? 2元(不找零)，2元 - 5分， 2元 - 1角，...... 5分(不找零)

接着验证该算法的贪心选择性和最优子结构性质，证明贪心算法可以获得最优解。

代码实现

import time

# 每种硬币的面值
coins = [0.05, 0.1, 0.2, 0.5, 1, 2]
# 每种硬币的数量
coin_num = []
s = 0

print("Separated by ‘,‘")
temp = input(‘Please enter the quantities of various change:‘)
coin_num0 = temp.split(‘,‘)

for i in range(len(coin_num0)):
    coin_num.append(int(coin_num0[i]))
    s += coins[i] * coin_num[i]

n_map = 
    ‘1‘: ‘One‘,
    ‘2‘: ‘Two‘,
    ‘3‘: ‘Three‘,
    ‘4‘: ‘Four‘,
    ‘5‘: ‘Five‘,
    ‘6‘: ‘Six‘,
    ‘7‘: ‘Seven‘,
    ‘8‘: ‘Eight‘,
    ‘9‘: ‘Nine‘,
    ‘10‘: ‘Ten‘


while True:
    time.sleep(0.2)
    sum = float(input(‘Please enter the amount of change you want:‘))
    # 当输入的总金额比收银员的总金额多, 无法进行找零
    if sum > s:
        print(‘The input amount is too large!‘)
        continue

    s = s - sum
    i = len(coins) - 1
    while i >= 0:
        if sum >= coins[i]:
            n = int(sum / coins[i])
            if n >= coin_num[i]:
                n = coin_num[i]
            # 关键, 令sum动态改变
            sum -= n * coins[i]
            print(‘%s %s-dollar COINS were used‘%(n_map.get(str(n)), n_map.get(str(coins[i]))))

        i -= 1
    break

算法学习——贪心算法之删数字（求最大值）(代码片段)

算法描述在给定的n位数字，删除其中的k位数字（k<n），使得最后的n-k为数字为最大值（原次序不变）算法思路考虑到是要移出数字，我们使用链表设计此算法较为方便，链表可以直接移出某个位置的元素使用贪心算法，每一... 查看详情

java数据结构&算法宁可累死自己,也要卷死别人18贪心算法(代码片段)

...,深圳K3上海,杭州,成都K4上海,天津K5杭州,大连贪心算法的核心思想:把所有需要覆盖的地区取集合从电台中取覆盖集合中地区最多的一个集合中去除已覆盖地区,继续匹配代码实现importjava.util.ArrayList;importjava.util.Arrays;importjava.util.Has... 查看详情

背包问题（贪心算法）(代码片段)

...这是背包问题，而不是0-1背包问题，背包问题可以用贪心算法进行求解，但0-1无法用贪心算法求解，需要用动态规划算法求解；首先对贪心算法做一下总结，以及它与动态规划算法的区别：贪心算法两个最重要的性质：（1）贪... 查看详情

贪心算法-第一节：贪心算法概述(代码片段)

文章目录一：贪心算法（1）概述（2）特点（3）框架二：典型贪心算法问题（1）无重叠区间①：题目描述②：解题思路③：完整代码（2）活动安排问题①：题目描述... 查看详情

matlab-贪心/贪婪算法(代码片段)

目录一、贪心算法的基本定义和特点二、贪心算法的基本步骤三、实例分析1.问题2.例子与分析3.代码编写（MATLAB版贪心算法）一、贪心算法的基本定义和特点贪心算法的英文是greedyalgorithm，又称贪婪算法，是一种... 查看详情

算法_贪心算法篇(代码片段)

LeetCode_跳跃游戏本文通过跳跃游戏的几个算法例题总结一下相关贪心算法，开始学习的阶段，借鉴好的算法思路并学习，也巩固一下最近学习的算法。（后续遇到贪心算法会续更~~）文章目录LeetCode_跳跃游戏前... 查看详情

算法_贪心算法篇(代码片段)

LeetCode_跳跃游戏本文通过跳跃游戏的几个算法例题总结一下相关贪心算法，开始学习的阶段，借鉴好的算法思路并学习，也巩固一下最近学习的算法。（后续遇到贪心算法会续更~~）文章目录LeetCode_跳跃游戏前... 查看详情

贪心算法(代码片段)

贪心策略　　总是做出当前做好的选择。　　贪心策略：将问题分成多个子问题；子问题求局部最优解；局部最优解组合成原问题的解。　　分类：简单贪心 区间贪心咖啡豆问题　题目描述FatMousepreparedMpoundsofcatfood,readytotrade... 查看详情

贪心算法回顾(代码片段)

各位好，贪心算法可以说是处处学到，被面试频频问道，接下来回顾以下，并上代码： 1packagecom.clb.ai.algorithm;23importjava.util.ArrayList;4importjava.util.List;5importjava.util.Map;6importjava.util.TreeMap;78/**9*贪心算法（又称贪婪算法）是指，在... 查看详情

背包问题（贪心算法）(代码片段)

　　贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。　　贪心算法还是比较好理解的一个算法，以前我也... 查看详情

贪心算法-纸币问题(代码片段)

从一个生活问题谈起先来看看生活中经常遇到的事吧——假设您是个土豪，身上带了足够的1、5、10、20、50、100元面值的钞票。现在您的目标是凑出某个金额w，需要用到尽量少的钞票。依据生活经验，我们显然可以采... 查看详情

算法-贪心算法详解(代码片段)

...题转换leetcode55跳跃游戏解答题目概述顾名思义，贪心算法或贪心思想采用贪心的策略，保证每次操作都是局部最优的，从而使最后得到的结果是全局最优的。引入钞票支付问题有1元、5元、10元、20元、100元的钞票无... 查看详情

算法笔记贪心算法(代码片段)

前言：对于贪心算法的学习主要以增加阅历和经验为主，也就是多做多积累经验，以下通过几个题目来介绍贪心算法的乐趣！文章目录1.贪心算法基本介绍2.题目题一：给定一个由字符串组成的数组strs，必... 查看详情

图--05---贪心算法prim算法kruskal算法(代码片段)

...生成，如何生成可参考右边的帮助文档文章目录贪心算法贪心算法----定义：使用切分定理找到最小生成树的一条边，不断的重复直到找到最小生成树的所有边贪心算法----原理:最小生成树的算法Prim算法切分规则：... 查看详情

python_分治算法贪心算法动态规划算法(代码片段)

文章目录一、分治算法思想1、基本算法思想2、寻找假币示例二、贪心算法1、思想2、最大不相容活动安排示例三、动态规划1、思想2、最大和路径3、背包问题4、动态规划和贪心算法的区别一、分治算法思想分治算法是一种化繁... 查看详情

算法导论——贪心算法(代码片段)

贪心算法（greedyalgorithm）是指，在每一步都做出当时看起来最佳的选择，也就是局部最优的选择，期望这样的选择能够导向全局最优解。所以并不是所有的问题都能得到全局最优解。        典型的例... 查看详情

贪心算法j题(代码片段)

Ignatiushasjustcomebackschoolfromthe30thACM/ICPC.Nowhehasalotofhomeworktodo.Everyteachergiveshimadeadlineofhandinginthehomework.IfIgnatiushandsinthehomeworkafterthedeadline,theteacherwillreducehisscor 查看详情

chatgpt教你算法——贪心算法(代码片段)

0.引言在计算机科学中，贪心算法是一种用来解决多阶段决策最优化问题的算法。它的名字来源于贪婪策略，即每一步都选择当前看来是最优的选择，而不考虑未来的影响。这种算法的优点在于它的简单性和速度，... 查看详情