锐客网

  1. 首页 > 生活百科 > it技术 > >

算法技巧|python算法技巧——贪心算法练习及掌握

Python算法学习贪心算法经验分享算法技巧

目录
【算法技巧|python算法技巧——贪心算法练习及掌握】1. 设计findcontentchildren(greedy, size)来判断出饼干可以满足多少小孩：
2. 设计carpooling(trips, capacity)判断是否一个车能接送所有旅客：
3. 旅游路线问题
4. 背包问题
5. 电台问题
1. 设计findcontentchildren(greedy, size)来判断出饼干可以满足多少小孩：

  • greedy为贪婪指数列表，列出每个小孩期待的饼干大小；如：greedy[1, 2]为第一个小孩期待饼干大小为1，第二个小孩期待饼干大小为2；
  • size为饼干大小列表；如：size[1, 2]为第一块饼干大小为1，第二块饼干大小为2；
def findcontentchildren(greedy, size): greedy.sort() size.sort() index = 0 ptr = 0 for g in greedy: while indexsize[index]: index += 1 if index

代码解析：
这个程序的设计方式就是先对greedy和size列表排序，然后使用g遍历greedy列表和size列表作比较，如果size[index]小于g，且index小于size的长度，index必须加1，相当于指标往后移。当找到size[index]大于g，表示可以满足一个小孩，就可以离开while循环了；
2. 设计carpooling(trips, capacity)判断是否一个车能接送所有旅客：
  • trips = [num_passengers, start_location, end_location]：num_passengers是旅客数量, start_location是上车站, end_location是下车站；
  • capacity是车辆的容量；
def carpooling(trips, capacity): car = [] for n, start, end in trips: car.append((start, n)) car.append((end, -n)) car.sort() people = 0 for c in car: people += c[1] if people>capacity: return False return Trueprint(carpooling([[2,1,6],[3,3,8]],4)) print(carpooling([[2,1,6],[3,3,8]],5)) print(carpooling([[3,2,6],[3,6,9],[8,3,9]],11))

3. 旅游路线问题
有一个旅游者想一次性游览这6个城市，请设计贪心算法，输入任意起点城市，都能得出最适当的拜访路线和最后的旅行距离：
算法技巧|python算法技巧——贪心算法练习及掌握
文章图片

def greedy(graph, cities, start): visited = [] visited.append(start) start_i = cities.index(start) distance = 0 for outer in range(len(cities)-1): graph[start_i][start_i] = INF min_dist = min(graph[start_i]) distance += min_dist end_i = graph[start_i].index(min_dist) visited.append(cities[end_i]) for inner in range(len(graph)): graph[start_i][inner] = INF graph[inner][start_i] = INF start_i = end_i return distance,visitedINF = 9999 cities = ['北京','天津','西安','武汉','上海','广州'] graph = [[0, 132,1120,1200,1463,1888], [ 132,0,1182,1367, 957,2100], [1120,1182,0,1035,1509,1950], [1200,1367,1035,0, 686,1030], [1463, 957,1509, 686,0,1705], [1888,2100,1950,1030,1705,0]] start = input('出发城市：') dist, visited = greedy(graph, cities, start) print('旅游顺序：',visited) print('旅游距离：',dist)

4. 背包问题
一个人有一个可以装10千克货物的背包，他到一个市场想最大价值的带走他想要的东西，请你用贪心算法帮他：
  • '手表'：(1500,1),
  • '手机'：(3500,7),
  • '平板'：(3800,5),
  • '电脑'：(4000,8),
  • '相机'：(2000,1),
  • '眼镜'：(1200,1.2),
  • '耳机'：(1000,1)
def greedy(things): length = len(things) things_list = [] things_list.append(things[length-1]) weights = things[length-1][1][1] for i in range(length-1, -1, -1): if things[i][1][1] +weights <= max_weight: things_list.append(things[i]) weights += things[i][1][1] return things_listthings = {'手表':(1500,1), '手机':(3500,7), '平板':(3800,5), '电脑':(4000,8), '相机':(2000,1), '眼镜':(1200,1.2), '耳机':(1000,1)} max_weight = 10 th = sorted(things.items(), key = lambda item:(item[1][0]/item[1][1])) t = greedy(th) print('贪婪选择下的商品如下：') for i in range(len(t)): print(*t[i])

5. 电台问题
某组织想要通过电台进行全国大部分省份的通信，而电台有地域性限制，且有一定成本，所以想用尽可能少的电台进行覆盖：
  • 电台1：湖北，安徽，江西；
  • 电台2：河南，湖北，湖南；
  • 电台3：浙江，安徽，江苏；
  • 电台4：安徽，山东，江西；
  • 电台5：江苏，天津，北京；
  • 电台6：广西，广东，福建；
  • 电台7：甘肃，山西，江西，山东；
def greedy(radios, cities): greedy_radios = set() while cities: greedy_choose = None city_cover = set() for radio, area in radios.items(): cover = cities & area if len(cover) > len(city_cover): greedy_choose =radio city_cover = cover cities -= city_cover greedy_radios.add(greedy_choose) return greedy_radioscities = set(['北京','天津','湖北', '安徽','江西','河南', '湖南','浙江','江苏', '山东','江西','广西', '广东','福建','甘肃']) radios ={} radios['电台1']=set(['湖北','安徽','江西']) radios['电台2']=set(['河南','湖北','湖南']) radios['电台3']=set(['广西','广东','福建']) radios['电台4']=set(['浙江','安徽','江苏']) radios['电台5']=set(['安徽','山东','江西']) radios['电台6']=set(['江苏','天津','北京']) radios['电台7']=set(['甘肃','山西','江西','山东']) print(greedy(radios, cities))

算法技巧专栏 https://blog.csdn.net/weixin_53919192/category_11761989.html算法技巧|python算法技巧——贪心算法练习及掌握
文章图片
https://blog.csdn.net/weixin_53919192/category_11761989.html

    推荐阅读


    上一篇：网络安全全栈课程|反弹shell方法

    下一篇：python|YOLOv5添加注意力机制