贪心算法（又名贪心算法）是指在解决一个问题的时候，总是做出当前好的选择。也就是说，在不考虑整体最优的情况下，他做的是某种意义上的局部最优解。贪心算法不保证一定会得到最优解，但是贪心算法的解是某些问题上的最优解。需要判断一个问题是否可以用贪心算法来计算。贪心算法与其他算法有明显的区别。动态规划每次都是对所有子问题的解进行综合得到当前最优解（全局最优解），而不是贪心选择；回溯法是尝试选择一个，如果选择错误，可以“gobackonit”，即回头再试一个。1找零问题假设店主需要找n元。硬币面额有100元、50元、20元、5元、1元。怎样找钱才能使需要的硬币数量最少？（注：没有10元100*3+50*1+20*1+5*1+1*1=375代码如下：#t表示店内找零的面额t=[100,50,20,5,1]#n表示n元defchange(t,n):m=[0for_inrange(len(t))]fori,moneyinenumerate(t):m[i]=n//money#divisiondirectiondownn=n%money#returnfromdivisionreturnm,nprint(change(t,376))#([3,1,1,1,1],0)2背包问题常见的背包问题包括整数背包和Part背包问题的描述。问题的描述大致是这样的。一个小偷在一家商店里找到了n件物品，第i件物品价值Vi元，重Wi公斤。他希望尽可能多地拿走价值，但是他的backpackcanonlyholdinguptoWkg.Whichitemsheshouldtaken?0-1Backpack:对于一件物品，小偷要么全部拿走，要么保留。你不能只拿走一部分，也不能拿走一个产品多次（产品为金条）得分背包：对于一个产品，小偷可以拿走其中的任何部分。（产品为金沙）示例：对于0-1knapsack和fractionalknapsack，贪心算法能不能得到最优解？为什么？显然，对于分数型背包，贪心算法一定能得到最优解。我们计算每个物品值的单位重量，然后按降序排列，然后开始取物品，只要你能装下所有该类型的物品，就可以全部放进去，如果装不下装满它们，您可以放入其中一些，直到背包装满为止。对于这个问题，很明显0-1的背包一定没有装满。即使偶然有可能，也不能满足所有0-1背包问题。0-1背包问题（又称整数背包问题）也可以分为两种：一种是每种类型的物品数量都是有限的（有界的）。一种是无界的，也就是想吃多少就吃多少，这两种都不能用贪心策略。0-1背包是典型的第一类整数背包问题。积分背包代码实现：#每个产品元组代表（价格，重量）goods=[(60,10),(100,20),(120,30)]#我们要先对产品进行排序，当然这里是排序goods.sort(key=lambdax:x[0]/x[1],reverse=True)#w表示背包的容量defractional_backpack(goods,w):#m表示每个产品带走了多少total_v=0m=[0for_inrange(len(goods))]fori,(prize,weight)inumerate(goods):ifw>=weight:m[i]=1total_v+=prizew-=weight#m[i]=1ifw>=weightelseweight/welse:m[i]=w/weighttotal_v+=m[i]*prizew=0breakreturnm,total_vres1,res2=fractional_backpack(goods,50)print(res1,res2)#[1,1,0.6666666666666666]1.3拼接最大数的问题有n个非负数，按照串接的方法串接成一个整数。如何连接成最大的整数？例如：32,94,128,1286,6,71最大可以串联的整数是94716321286128注1：字符串比较数的大小和整数比较数的大小是不一样的！！！字符比较字符串的大小首先是看第一个数字，大的比较大，但是长字符串和短字符串怎么比较呢？比如128和1286的比较如下：#简单：比较两个相等的数字时a='96'b='97'a+bifa>belseb+a#比较后面不等的数字时，如何使用贪心算法？#我们改造思路，拼接字符串，比较结果a='128'b='1286'#字符串加法a+b='1281286'b+a='1286128'a+bifa+b>b+aelseb+a进行数字拼接的代码如下：fromfunctoolsimportcmp_to_keyli=[32,94,128,1286,6,71]defxy_cmp(x,y):#其中1表示x>y，-1,0与ifx相同+y
