📰 基本概念

对于一组数据，定义了限定值（比如重量不大于100KG）和期望值（物品总价值最高），希望从中选取几个数据，在满足限定值的情况下，期望值最大。

贪心算法每一步都会采取当前状态下最有利的选择，从而希望得到最优解。但由于前面的选择会影响后面的选择，有时候期望终究是期望，无缘全局最优解。

🔎 实例分析

（1）分糖果

• 向n个孩子分m个糖果，每个孩子对糖果的需求不一样，每个糖果的大小不一样，n>m。只有当分到的糖果大于其需求时，该孩子才得到满足。如何分配糖果，尽可能满足最多数量的孩子。
• 限制值：糖果个数m，期望值：得到满足的孩子数量
• 按照糖果需求高低和糖果大小分别对孩子和糖果进行排序，从糖果需求最小的孩子开始分配糖果，然后每次从剩下的孩子中选择对糖果需求最小的孩子，从剩下的糖果中拿给他满足其需求的最小糖果。

（2）钱币找零

• 有 1 元、2 元、5 元、10 元、20 元、50 元、100 元这些面额的纸币，它们的张数分别是 c1、c2、c5、c10、c20、c50、c100。现在要用这些钱来支付 K 元，最少要用多少张纸币呢？

• 限制值：支付的金额K，期望值：所用纸币的数量

• 从面额最大的纸币开始，不够的话，面额次大的补齐

（3）区间覆盖

• 有n个期间，区间的起始端点和结束端点分别是[l1, r1]，[l2, r2]，[l3, r3]，……，[ln, rn]。从这 n 个区间中选出一部分区间，这部分区间满足两两不相交（端点相交的情况不算相交），最多能选出多少个区间呢？
• 限制值：选中的区间两两不相交，期望值：选中的区间数量
• 根据起始端点从小到大对区间进行排序，每次选择左端点跟之前已经覆盖的区间不重合的、且右端点又尽量小的区间，这样可以让剩下的未覆盖区间尽可能的大，就可以放置更多的区间。
• 场景：任务调度，教师排课

（4）霍夫曼编码

• 不等长编码，出现频率低的字符编码长度大，出现频率高的字符编码长度小
• 将每个字符看作一个节点，并且辅带着把频率放到优先级队列中。我们从队列中取出频率最小的两个节点 A、B，然后新建一个节点 C，把频率设置为两个节点的频率之和，并把这个新节点 C 作为节点 A、B 的父节点。最后再把 C 节点放入到优先级队列中。重复这个过程，直到队列中没有数据。
• 左子节点的边标记为 0，右子节点的边标记为 1，从根节点到叶节点的路径就是叶节点对应字符的霍夫曼编码。

（5）思考题

• 在一个非负整数 a 中，我们希望从中移除 k 个数字，让剩下的数字值最小，如何选择移除哪 k 个数字呢？

  • 限制值：删除数字的位数，或者说删除后还剩几位，期望值：删除数字后的值

  • 正确解法：从最高位开始，比较低一位数字，高位数字大，则舍弃；低位数字大，则向右移一位继续比较两个数字，直到高位大于低位达到移除条件，循环k次

    class Solution:
        def deleteNumber(self, a: int, k: int) -> int:
            temp=list(str(a))     # 将字符串转换为列表
            for i in range(k):            
                for j in range(len(temp)-1):
                    if temp[j] > temp[j+1]:
                        del temp[j]
                        break # 跳出第二个for循环
    
            return(''.join(temp))    
    
    a=Solution()
    print(a.deleteNumber(76394288,3))

• ！！！错误解法：对a的数字进行排序，删除最大的K个数字。

  class Solution:
      def deleteNumber(self, a: int, k: int) -> int:
          temp=[]
          temp2=[]
          length=len(str(a))
          
          for i in str(a):
              temp.append(i)
          temp.sort()
  
          for i in str(a):
              if i in temp[:length-k]:
                  temp2.append(i)
          return(int(''.join(temp2)))  # 列表转字符串，再转整型
          
  a=Solution()
  print(a.deleteNumber(7639428,3))

• 假设有 n 个人等待被服务，但是服务窗口只有一个，每个人需要被服务的时间长度是不同的，如何安排被服务的先后顺序，才能让这 n 个人总的等待时间最短？

  • 限制值：等待服务的人数，服务窗口数量，期望值：总的等待时长
  • 按需求时间排序，从短到长开始。