贪心算法通常也会结合其他知识点一并考察（如排序、栈、堆排序等）
（预备知识）贪心法求解钞票问题
这里有几种不同面额的钞票，1元、5元、10元、20元、100元、200元的钞票无穷多张，现在使用这些钞票去支付X元的面额，问最少需要多少张？
例如X=628，我们通常会尝试从面额最大的钞票（200元）开始尝试，此时发现200元的钞票只能使用3张，此时剩余的面额是628-3*200=28元，再依次查看次最大面额100元，因为100>28，因此不能用100元构成结果，再次以查看20元，发现可以使用1张，······，以此类推，我们得到最终的最小钞票张数的结果是8（628 = 200*3 + 20*1 + 5*1 + 1*3）
如果用暴力枚举的方法，可以验证8确实是最优结果。我们这里使用的就是“贪心”的策略，那么从算法的层面如何解读呢？为什么这个示例中用贪心策略能够得到最优解呢？我们这里引入贪心的思想。
（贪心）
定义：遵循某种规律，不断地选取当前最优策略的设计方法，就是贪心的思想。
思考：为什么上述钞票的例子使用贪心可以得到全局最优解？
原因：因为上述的钞票列表中任意面额都是比自己小的面额的整数倍，每当使用一张较大面额的钞票时，一定需要更多的较小面额钞票取代，因此可以保证：
当前最优解就是全局最优解
，即
贪心成立
。
变形：若此时增加一张7元面额的钞票，贪心是否还成立？
此时仍然使 X = 628，使用贪心策略的话，得到的解是8 （200*3 + 20*1 + 5*1 + 1*3），然而实际的最优解是6（200*3 + 20*1 + 7*1 + 1*1），此时贪心不成立，那么如何解决贪心不成立的问题，通常用动态规划求解。
此处，贴出一个动态规划的代码：
def money_change_dp(money_value, target):
dp = [0] * (target+1)
money_value = sorted(money_value)
for i in range(1, target+1):
for val in money_value:
if i >= val:
if dp[i] == 0 or dp[i-val]+1 < dp[i]:
dp[i] = dp[i-val]+1
return dp[target]
if __name__ == '__main__':
l = [5, 7, 100, 20, 200, 10, 1]
d = money_change_dp(l, 628)
print(d)而贪心策略的实现，则如下所示：
from math import floor
def get_least_count(money_value, target):
sort_money = sorted(money_value, reverse=True)
money_count_dic = {}
count = 0
for val in sort_money:
use = floor(target/val)
if use > 0:
count += use
target = target%val
money_count_dic[val] = use
return money_count_dic, count这里简单总结一下，贪心算法的成立是有条件的，需要满足某种情况（比如倍数关系等）。但是，一旦我们寻找到了贪心的规律，贪心就可以帮助我们快速高效地解决很多困难的问题。若不使用贪心，可能需要用回溯、动态规划、暴力枚举等方法，势必会造成较大的开销。