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

柔情只为你懂 2023-09-29 12:57 48阅读 0赞

**目录**

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 index<len(size) and g>size[index]:
                index += 1
            if index<len(size) and g<=size[index]:
                ptr += 1
                index += 1
        return ptr
    print(findcontentchildren([2,1,3],[1,1]))
    print(findcontentchildren([1,3],[1,2,3]))

**代码解析：**

> 这个程序的设计方式就是先对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 True
    
    print(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个城市，请设计贪心算法，输入任意起点城市，都能得出最适当的拜访路线和最后的旅行距离：

![2d59233167cb42fc902f1519aa234573.png][]

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,visited
    
    INF = 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_list
    
    things = {'手表':(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_radios
    
    cities = 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![icon-default.png_t_M3K6][]https://blog.csdn.net/weixin\_53919192/category\_11761989.html][https_blog.csdn.net_weixin_53919192_category_11761989.html_icon-default.png_t_M3K6_https_blog.csdn.net_weixin_53919192_category_11761989.html]

[2d59233167cb42fc902f1519aa234573.png]: https://img-blog.csdnimg.cn/2d59233167cb42fc902f1519aa234573.png
[icon-default.png_t_M3K6]: https://csdnimg.cn/release/blog_editor_html/release2.1.0/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=M3K6
[https_blog.csdn.net_weixin_53919192_category_11761989.html_icon-default.png_t_M3K6_https_blog.csdn.net_weixin_53919192_category_11761989.html]: https://blog.csdn.net/weixin_53919192/category_11761989.html