极の都市---贪心算法

秒速五厘米 2022-12-21 03:28 127阅读 0赞

### 目录 ###

*   *  一：逃脱游戏：
     *  二：找硬币问题：
     *  三：活动问题：
     *  四：最小数字问题：
     *  五：两个数字的最小和:
     *  六：以最低的成本连接绳索：
     *  七：最小平台数：
     *  八：部分背包问题：
     *  九：分蛋糕问题：
     *  十：将板子分割成正方形最小的成本：
     *  十一：字典中的最小数组：

## 一：逃脱游戏： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center]  
1： 思路一：递归操作

from enum import Enum
    
    class Index(Enum):
        GOOD = 1
        BAD = 2
        UNKNOW = 3
    
    def can_jump(nums):
        # 创建另外一个列表，根传入的nums列表数量一致。
        memo = [Index.UNKNOW] * len(nums)
        # 将最后一个设置成可以到达
        memo[-1] = Index.GOOD
        # 从倒数第二个位置，逆序遍历，到0位置，包括0，所以是-1
        for i in range(len(nums) -2 , -1, -1):
            # 获取从当前位置最远到达的距离
            furthestJump = min(i + nums[i], len(nums)-1)
            # 遍历能够到达的位置中有没有True
            for j in range(i+1, furthestJump +1):
                # 如果找到，将当前位置设置成True
                if memo[j] == Index.GOOD:
                    memo[i] = Index.GOOD
                    break
            # 遍历如果没有，则当前位置设置成False
            return memo[0] == Index.GOOD
    
    
    nums = [2, 3, 1, 1, 4]
    can = can_jump(nums)
    print(can)

2：思路二：动态规划DP

from enum import Enum
    
    class Index(Enum):
        GOOD = 1
        BAD = 2
        UNKNOW = 3
    
    def can_jump(nums):
        # 创建另外一个列表，根传入的nums列表数量一致。
        memo = [Index.UNKNOW] * len(nums)
        # 将最后一个设置成可以到达
        memo[-1] = Index.GOOD
        # 从倒数第二个位置，逆序遍历，到0位置，包括0，所以是-1
        for i in range(len(nums) -2 , -1, -1):
            # 获取从当前位置最远到达的距离
            furthestJump = min(i + nums[i], len(nums)-1)
            # 遍历能够到达的位置中有没有True
            for j in range(i+1, furthestJump +1):
                # 如果找到，将当前位置设置成True
                if memo[j] == Index.GOOD:
                    memo[i] = Index.GOOD
                    break
        # 看看初始位置能否变成True,如果可以就成功，如果是False说明无法到达。
        return memo[0] == Index.GOOD
    
    
    nums = [2, 3, 1, 1, 4]
    can = can_jump(nums)
    print(can)

3： 思路三：贪心算法：Greedy

def can_jump(nums):
        last_pos = len(nums) - 1
        for i in range(len(nums)-1, -1, -1):
            if i + nums[i] >= last_pos:
                last_pos = i
    
        return last_pos == 0
    
    nums = [2, 3, 1, 1, 4]
    can = can_jump(nums)
    print(can)

## 二：找硬币问题： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center 1]

def minCoins(V):
        available = [1, 2, 5, 10, 20, 50, 100, 500, 1000]
        result = []
        for i in available[:: -1]:
            while(V >= i):
                V -= i
                result.append(i)
    
        return result
    
    V = 93
    result = minCoins(V)
    print(result)

## 三：活动问题： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center 2]

> 解题思路：  
> 1： 根据结束时间从小到大排序。  
> 2：每次选择，开始时间大于自己结束时间的最早结束的那个（第一个）。

def printMaxActivities(acts):
        # 对一个列表套元组的根据元组的1号位置排序，从小到大
        # key 指定可迭代对象中的一个元素来排序
        sort_acts = sorted(acts, key=lambda tup: tup[1])
        # 第一个应该选择的时间段
        prev = sort_acts[0]
        print(prev)
        # 遍历所有的时间段
        for curr in sort_acts:
            # 判断下一个的初始时间是不是大于上一个的结束时间
            if curr[0] >= prev[1]:
                print(curr)
                prev = curr
    
    acts = [(0,6), (3, 4), (1,2), (5, 7), (8, 9), (5, 9)]
    
    printMaxActivities(acts)

## 四：最小数字问题： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center 3]

> 问题描述：给你两个数分别是 S 和 m ， m表示几位数，S表示每位数之和。例如 m = 2, s= 9,则表示两位数，个位+十位=9。现在求最小的符合的数是多少？

> 思路： 最大的数的特征是，首位肯定不能是0，尾位争取最大，因此可以先让m减一，留给最高位。然后从后向前，依次判断是不是S大于9，如果大于9则，赋值9，否则就赋值剩余的。最后再在最高位加一。

def findSmallests(m, s):
        # 如果和是0，位数是1，则就是0
        if (s == 0):
            if (m == 1):
                print("Smallest number is 0")
            else:
                print("Not possible")
        # 如果几个数之和大于9乘以几位数，则不可能。
        if (s > 9 * m):
            print("Not Possible")
            return
        # 得到一个初始化全为0的列表，列表位数和数位数相同。
        res = [0 for i in range(m+1)]
    
        # 1：先将和-1，留给首位最后加上，这样保证首位不为0
        s -= 1
        # 2：从最后一位遍历到1号位
        for i in range(m-1, 0, -1):
            # 如果大于9就赋值这位9
            if (s > 9):
                res[i] = 9
                s -= 9
            # 如果不大于9，则赋值剩余数
            else:
                res[i] = s
                s = 0
                break
        # 最后第一位等于剩余数+1
        res[0] = s + 1
        print("Smallest number is ", end="")
        for i in range(m):
            print(res[i], end="")
    
    s = 9 # 几位数之和
    m = 2 # 几位数
    findSmallests(m, s)

## 五：两个数字的最小和: ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center 4]

> 问题描述：一个列表，将里面数，组成两个最小的数，输出他们的和。  
> 思路：先进行排序，然后从小到大，依次给两个数后面追加。

# 导入堆排序
    import heapq
    
    def minSum(a):
        # 对数据进行堆排序
        heapq.heapify(a)
        num1 = 0
        num2 = 0
        # 只要列表不为空
        while a:
            # 弹出数据 + 之前数据*10，相当于后面增加弹出来的数据
            num1 = num1 * 10 + heapq.heappop(a)
            # 如果a还有数据，则给num2页增加
            if a:
                num2 = num2 * 10 + heapq.heappop(a)
        return num1 + num2
    
    
    a = [6, 8, 4, 5, 2, 3]
    sum = minSum(a)
    print(sum)

## 六：以最低的成本连接绳索： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center 5]

> 思路：要想成本最低，则需要每次都连接成本最小的。连接次数固定，我们应该尽量多使用数小的连接，少使用数大的。如果每次先连接最大的，则大数会频繁的被使用。

堆：取数字和插入数字都是 log(n)

import heapq
    
    def ropeCost(ropes):
        # 对数据进行堆排序
        heapq.heapify(ropes)
        total = 0
    
        # 只要数组还有数据
        while ropes:
            # 弹出两个最小的值
            first = heapq.heappop(ropes)
            second = heapq.heappop(ropes)
            local = first + second
            total += local
            if not ropes:
                break
            # 将两数之和再插入堆中
            heapq.heappush(ropes, local)
    
        return total
    
    ropes = [4, 3, 2, 6]
    total = ropeCost(ropes)
    print(total)

## 七：最小平台数： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center 6]

def findplarfrom(arr, dep, n):
        arr.sort()
        dep.sort()
    
        plat_needed = 0
        result = 0
        i = 0
        j = 0
        while(i < n and j < n):
            if (arr[i] < dep[j]):
                plat_needed += 1
                i += 1
                result = max(result, plat_needed)
            elif (arr[i] == dep[j]):
                i += 1
                j += 1
            else:
                plat_needed -= 1
                j += 1
    
        return result
    
    arr = [900, 940, 950, 1100, 1500, 1800]
    dep = [910, 1200, 1120, 1130, 1900, 2000]
    n = len(arr)
    count = findplarfrom(arr, dep, n)
    print(count)

## 八：部分背包问题： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center 7]

def maxPackage(capacity, weights, values):
        # 按照性价比排序，逆序
        valuePerWeight = sorted([[v/w, w, v]for v, w in zip(values, weights)], reverse=True)
        print(valuePerWeight)
        # 记录总价值
        totalCost  = 0
        # 遍历列表套列表
        for tup in valuePerWeight:
            # 如果剩余背包容量，大于总容量，背包容量减这个全部容量，价值加上全部价值。
            if capacity >= tup[1]:
                capacity -= tup[1]
                totalCost += tup[2]
            # 如果背包容量不足全装下，则装部分，总价值加上单价乘以背包剩余数量。
            else:
                totalCost += capacity * tup[0]
                break
            return totalCost
    
    n  = 3
    capacity = 50
    values = [72, 100, 120]
    weights = [24, 50, 30]
    totalCost = maxPackage(capacity, weights, values)
    print(totalCost)

## 九：分蛋糕问题： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center 8]

> 分析：  
> 我们可以先将孩子要求的蛋糕尺寸进行从小到大排序，然后遍历蛋糕从小到大依次尝试。

def demo_01(list1, list2):
        sorted(list1)
        sorted(list2)
        count = 0
        i = 0
        j = 0
        lenth1 = len(list1)
        lenth2 = len(list2)
        while True:
            if i >= lenth1:
                break
            elif j >= lenth2:
                break
    
            elif list1[j] >= list2[i]:
                count += 1
                i += 1
                j += 1
            else:
                j += 1
        return count
    
    list1 = [4, 6, 7, 8, 2, 9]
    
    list2 = [3, 5, 6, 12, 4, 1]
    
    count = demo_01(list1, list2)
    print(count)

## 十：将板子分割成正方形最小的成本： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center 9]

> 思路：每次切割最大的。

## 十一：字典中的最小数组： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center 10]

def demo_02(arr, n, k):
        for i in range(n-1):
            pos = i
            for j in range(i+1, n):
                if (j -i > k):
                    break
                if (arr[j] < arr[pos]):
                    pos = j
    
            for j in range(pos, i, -1):
                arr[j], arr[j-1] = arr[j-1], arr[j]
    
            k -= pos -i
    
    n, k = 5, 3
    arr = [7, 6, 9, 2, 1]
    demo_02(arr, n, k)
    
    for i in range(n):
        print(arr[i], end=" ")

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/0de5ff0cdbb24f00806f38fcc4d6977a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/ffd6f7b05aa743de9ae106c46e8be16b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/0b178d962fe047f6a963e903513bb014.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/a9126d862aa24b458b671c42370af90d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/2be387ff0ff341ff93fb7baac1f158d3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221120/8e74abaaee4a405a8d0eeabab3a7d723.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221120/20a478fc4c4a4570b85a16424d2a4c6b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221120/1264404008ee4a1db3b05bf0078bb221.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221120/1527e477e562471597c2069f5be673f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221120/c401b004ed6548c4b910eb11546525f8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221120/05e115d3fd624bf5a109ac26a6545061.png