设为首页 - 加入收藏 92站长网 (http://www.92zhanzhang.com)- 国内知名站长资讯网站,提供最新最全的站长资讯,创业经验,网站建设等!
热搜: 为什么 中国 苹果 系统
当前位置: 首页 > 运营中心 > 建站资源 > 优化 > 正文

Python常用的算法——贪心算法(又称贪婪算法),你知道吗?

发布时间:2019-10-30 16:24 所属栏目:[优化] 来源:编程只为
导读:贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是好的选择。也就是说,不从整体最优上加以考虑,他所做出的的时在某种意义上的局部最优解。 贪心算法并不保证会得到最优解,但是在某些问题上贪心算法的解就是最优解。要会判断一个问题能

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

贪心算法并不保证会得到最优解,但是在某些问题上贪心算法的解就是最优解。要会判断一个问题能否用贪心算法来计算。贪心算法和其他算法比较有明显的区别,动态规划每次都是综合所有问题的子问题的解得到当前的最优解(全局最优解),而不是贪心地选择;回溯法是尝试选择一条路,如果选择错了的话可以“反悔”,也就是回过头来重新选择其他的试试。

Python常用的算法——贪心算法(又称贪婪算法),你知道吗?

1 找零问题

假设商店老板需要找零 n 元钱,钱币的面额有100元,50元,20元,5元,1元,如何找零使得所需钱币的数量最少?(注意:没有10元的面额)

那要是找376元零钱呢? 100*3+50*1+20*1+5*1+1*1=375

代码如下:

  1. #?t表示商店有的零钱的面额?
  2. t?=?[100,?50,?20,?5,?1]?
  3. ??
  4. #?n?表示n元钱?
  5. def?change(t,?n):?
  6. ?m?=?[0?for?_?in?range(len(t))]?
  7. ?for?i,?money?in?enumerate(t):?
  8. ?m[i]?=?n?//?money?#?除法向下取整?
  9. ?n?=?n?%?money?#?除法取余?
  10. ?return?m,?n?
  11. ??
  12. print(change(t,?376))?#?([3,?1,?1,?1,?1],?0)?

2 背包问题

常见的背包问题有整数背包和部分背包问题。那问题的描述大致是这样的。

一个小偷在某个商店发现有 n 个商品,第 i 个商品价值 Vi元,重 Wi 千克。他希望拿走的价值尽量高,但他的背包最多只能容纳W千克的东西。他应该拿走那些商品?

  • 0-1背包:对于一个商品,小偷要么把他完整拿走,要么留下。不能只拿走一部分,或把一个商品拿走多次(商品为金条)
  • 分数背包:对于一个商品,小偷可以拿走其中任意一部分。(商品为金砂)

举例:

python常用的算法——贪心算法(又称贪婪算法),你知道吗?

对于 0-1 背包 和 分数背包,贪心算法是否都能得到最优解?为什么?

显然,贪心算法对于分数背包肯定能得到最优解,我们计算每个物品的单位重量的价值,然后将他们降序排序,接着开始拿物品,只要装得下全部的该类物品那么就可以全装进去,如果不能全部装下就装部分进去直到背包装满为止。

而对于此问题来说,显然0-1背包肯定装不满。即使偶然可以,但是也不能满足所有0-1背包问题。0-1背包(又叫整数背包问题)还可以分为两种:一种是每类物品数量都是有限的(bounded)。一种是数量无限(unbounded),也就是你想要的多少有多少,这两种都不能使用贪心策略。0-1背包是典型的第一种整数背包问题。

分数背包代码实现:

  1. #?每个商品元组表示(价格,重量)?
  2. goods?=?[(60,?10),?(100,?20),?(120,?30)]?
  3. #?我们需要对商品首先进行排序,当然这里是排好序的?
  4. goods.sort(key=lambda?x:?x[0]/x[1],?reverse=True)?
  5. ??
  6. #?w?表示背包的容量?
  7. def?fractional_backpack(goods,?w):?
  8. ?#?m?表示每个商品拿走多少个?
  9. ?total_v?=?0?
  10. ?m?=?[0?for?_?in?range(len(goods))]?
  11. ?for?i,?(prize,?weight)?in?enumerate(goods):?
  12. ?if?w?>=?weight:?
  13. ?m[i]?=?1?
  14. ?total_v?+=?prize?
  15. ?w?-=?weight?
  16. ?#?m[i]?=?1?if?w>=?weight?else?weight?/?w?
  17. ?else:?
  18. ?m[i]?=?w?/?weight?
  19. ?total_v?+=?m[i]*prize?
  20. ?w?=?0?
  21. ?break?
  22. ?return?m,?total_v?
  23. ??
  24. res1,?res2?=?fractional_backpack(goods,?50)?
  25. print(res1,?res2)?#?[1,?1,?0.6666666666666666]?
  26. 1.3?拼接最大数字问题?

有 n 个非负数,将其按照字符串拼接的方式拼接为一个整数。如何拼接可以使得得到的整数最大?

例如:32, 94, 128, 1286, 6, 71 可以拼接成的最大整数为 94716321286128.

注意1:字符串比较数字大小和整数比较数字大小不一样!!! 字符串比较大小就是首先看第一位,大的就大,可是一个字符串长,一个字符串短如何比较呢?比如128和1286比较

思路如下:

# 简单的:当两个等位数相比较

  1. a?=?'96'?
  2. b?=?'97'?
  3. ??
  4. a?+?b?if?a?>?b?else?b?+?a?

# 当出现了下面的不等位数相比较,如何使用贪心算法呢?

【免责声明】本站内容转载自互联网,其相关言论仅代表作者个人观点绝非权威,不代表本站立场。如您发现内容存在版权问题,请提交相关链接至邮箱:bqsm@foxmail.com,我们将及时予以处理。

网友评论
推荐文章