你听说过贪心算法,但你听说过反悔贪心算法吗?

举报
Xxy_1008 发表于 2024/07/30 10:20:50 2024/07/30
【摘要】 数据结构的运用:使用集合 seen 来快速判断元素的种类是否已经出现,利用列表 ll 存储重复种类的元素。 贪心算法的思想:先选择前 k 个利益最大的元素,然后通过逐步替换来尝试优化结果,体现了贪心选择局部最优以期望达到全局最优的思路。 逻辑推理和计算能力:在计算优雅度、判断是否替换元素以及更新相关变量时,需要准确的逻辑推理和计算。

什么是反悔贪心算法?

反悔贪心是一种算法思想或技巧,它包含“反悔”和“贪心”两个操作。
贪心算法通常只能得到局部最优解,而反悔贪心则是在要求全局最优解时,通过“反悔”操作来解决贪心算法的不足。其思想是每次都进行操作,在以后出现更优情况时再取消之前的操作。
一般来说,可以使用堆来存储选择的元素,堆顶通常是最劣解。常见的有两种情况:一种是符合某种条件时,将元素推入堆,并计算答案;另一种是不符合条件时,与堆顶进行比较并做出相应操作。
以下通过一些例题来进一步理解反悔贪心算法:
  • cf865d buylowsellhigh:已知接下来 n 天的股票价格,每天可以买入当天的股票、卖出已有的股票或者什么都不做,求 n 天之后的最大利润。一种贪心策略是在最低点买入,最高点卖出。可以用一个堆来记录今天之前的最小值,将每天的价格都当作买入价格推入堆中。当当前卖出价格大于最低价格(堆顶价格)时,意味着可以进行卖出操作,将当前价格和堆顶价格相减,累计答案,然后弹出堆顶(即取消之前的买入操作,也就是“反悔”),再将当前价格推入堆(进行“反悔”操作,将其当作新的买入价格)。因为若后面还有更优的卖出价格 y,之前的买入价格为 z,那么最优解 y-z 等于 (x-z)+(y-x),其中 x 为当前卖出价格。
  • p2209 (usaco13open) fuel economy s:要从起始点行驶到终点,途中有多个加油站,每个加油站有油价和到下一个加油站(或终点)的距离,汽车的油箱容量为 g,起始时有 b 个单位的油。首先判断无解的情况,如 b 个单位的油无法到达第一个加油站,或存在两个相邻加油站之间的距离大于 g 等。然后进行反悔贪心操作,为了从第 i 个加油站到第 i+1 个加油站(或终点),都需要加满油(贪心操作);而第 i 个加油站到第 i+1 个加油站之间多余的油,可以退掉(反悔操作)。在使用油时,优先使用单位价格低的油,使总花费最小。
  • p2949 (usaco09open) work scheduling:有 n 项工作,每项工作有截止时间 d_i 和完成可获得的利润 p_i,求最大可获得的利润。可以先按截止时间为第一关键字、利润为第二关键字进行排序,然后使用一个反悔堆(小根堆)来维护最优解。若当前工作满足截止时间条件,且当前利润比原来堆顶的最优解更优,就更新全局最优解,将原来的最优解弹出堆,放入当前利润;否则不做操作。若不满足截止时间条件,就直接将当前利润放入堆中更新全局最优解。
总的来说,反悔贪心算法通过巧妙地结合贪心策略和反悔操作,在一些问题中能够有效地找到全局最优解,不过具体的实现方式可能因问题而异,需要根据具体情况进行分析和设计。同时,使用堆或其他数据结构来维护中间状态,以便快速进行反悔和更新最优解。
在实际应用中,需要仔细分析问题的特点和约束条件,确定如何进行贪心选择以及如何进行反悔操作,以达到全局最优解的目标。这种算法思想在一些特定问题中能够提供高效的解决方案,但并非适用于所有情况,需要根据具体问题进行选择和应用。

今天的目的就是基于反悔贪心算法给大家找一道实例题目,便于大家学习这个算法。

2813.子序列最大优雅度【困难

题目:

给你一个长度为 n 的二维整数数组 items 和一个整数 k 。

items[i] = [profiti, categoryi],其中 profiti 和 categoryi 分别表示第 i 个项目的利润和类别。

现定义 items 的 子序列 的 优雅度 可以用 total_profit + distinct_categories2 计算,其中 total_profit 是子序列中所有项目的利润总和,distinct_categories 是所选子序列所含的所有类别中不同类别的数量。

你的任务是从 items 所有长度为 k 的子序列中,找出 最大优雅度 。

用整数形式表示并返回 items 中所有长度恰好为 k 的子序列的最大优雅度。

注意:数组的子序列是经由原数组删除一些元素(可能不删除)而产生的新数组,且删除不改变其余元素相对顺序。


示例 1:

输入:items = [[3,2],[5,1],[10,1]], k = 2
输出:17
解释:
在这个例子中,我们需要选出长度为 2 的子序列。
其中一种方案是 items[0] = [3,2] 和 items[2] = [10,1] 。
子序列的总利润为 3 + 10 = 13 ,子序列包含 2 种不同类别 [2,1] 。
因此,优雅度为 13 + 22 = 17 ,可以证明 17 是可以获得的最大优雅度。 

示例 2:

输入:items = [[3,1],[3,1],[2,2],[5,3]], k = 3
输出:19
解释:
在这个例子中,我们需要选出长度为 3 的子序列。 
其中一种方案是 items[0] = [3,1] ,items[2] = [2,2] 和 items[3] = [5,3] 。
子序列的总利润为 3 + 2 + 5 = 10 ,子序列包含 3 种不同类别 [1, 2, 3] 。 
因此,优雅度为 10 + 32 = 19 ,可以证明 19 是可以获得的最大优雅度。

示例 3:

输入:items = [[1,1],[2,1],[3,1]], k = 3
输出:7
解释:
在这个例子中,我们需要选出长度为 3 的子序列。
我们需要选中所有项目。
子序列的总利润为 1 + 2 + 3 = 6,子序列包含 1 种不同类别 [1] 。
因此,最大优雅度为 6 + 12 = 7 。


提示:

  • 1 <= items.length == n <= 10**5
  • items[i].length == 2
  • items[i][0] == profiti
  • items[i][1] == categoryi
  • 1 <= profiti <= 10**9
  • 1 <= categoryi <= n
  • 1 <= k <= n


分析问题:

        解这道题主要还是要有一定的思维能力,对贪心算法有一定的知识储备。因为这道题考察的内容确实有点多,在它的标签里列出了 贪心,栈,数组,哈希表,排序,堆(优先队列);可见这题考的内容之丰富,不过不用慌,在Python中列表可以充当大部分的数据结构,把列表运用好可以解决大多数问题。

那么这道题的话思路如下:

先把items按照利润大小排序(假设从大到小排序),然后先取前k个,计算出当前的value值;

然后考虑k+1以及之后的元素,首先要明白k+1后面的元素的利润值都是低于之前的任何一个的,那么分类讨论:

  • 如果k+1的种类存在于前k个元素中,那么把k+1加进去没有任何意义,种类重复利润还少,直接跳过即可。
  • 如果k+1的种类不存在于前k个元素中,那么我们要选一个种类重复的且利润最小的元素出来和他交换,这时候利润虽然减小了但是种类+1了,记录此时的a_value值,于原value值相比,谁大取谁作为value。

        按照这个思路,往下遍历,计算优雅度,取最大值即可。 不过要注意的是这里要记录种类重复的元素,以及将他们按照利润大小排序。这里可以直接用一个列表和一个集合实现,因为遍历的顺序是按照利润从大到小,所以加入到ls里面的元素的顺序一定是按照利润值从大到小的,直接将其翻转,先拿小的交换,这里需要一个指针,交换一次指针向前走一步,标记要被交换的元素。接下来看具体的代码实现:


代码实现:

class Solution:
    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:
        items.sort(key= lambda items:items[0],reverse=True)
        ls=items[:k] # 先按利益大小取前k个最大的元素
        seen,ll,su=set(),[],0 # seen用来标记出现过的种类
        for i,j in ls:
            if j not in seen: seen.add(j)
            else: ll.append([i,j])
            su+=i
        value=su+len(seen)**2  # 计算当前最大优雅度
        if len(ll)==0: return value
        ll,re=ll[::-1],0  # re 指针 用来标记要和ll中的哪个元素比较
        for q in items[k:]:
            if q[1] not in seen and re<=len(ll)-1:
                key=q[0]-ll[re][0]
                seen.add(q[1])
                su+=key
                re+=1
                a_va=su+(len(seen))**2
                if a_va>value:
                    value=a_va
        return value


总结:

代码逐行解释:

  1. 函数定义

    • 定义了名为 findMaximumElegance 的函数,接受 items 列表和整数 k 作为参数。
  2. 初始化操作

    • 对 items 按照第一项(利益大小)进行降序排序。
    • 取出前 k 个元素存储在 ls 列表中。
    • 创建空集合 seen 用于标记出现过的种类。
    • 创建空列表 ll 用于存储重复种类的元素。
    • 初始化变量 su 为 0,用于累计利益总和。
  3. 计算初始优雅度

    • 遍历 ls 中的每个元素 [i, j] ,如果 j 不在 seen 中,将其添加到 seen 中;否则,将该元素添加到 ll 中。
    • 累加 ls 中元素的利益到 su 。
    • 计算初始优雅度 value 为 su + len(seen) ** 2 。
  4. 处理剩余元素以优化优雅度

    • 如果 ll 不为空,将其反转。
    • 遍历 items 中 k 之后的元素 q 。
    • 如果 q 的种类不在 seen 中且 re 指针未超出 ll 的范围,计算用 q 替换 ll[re] 带来的利益变化 key 。
    • 更新 seen 、 su ,计算新的优雅度 a_va 。
    • 如果 a_va 大于当前的 value ,更新 value 。
  5. 返回结果

    • 函数最终返回计算得到的最大优雅度 value 。

 考查内容:

  1. 排序算法的应用:通过对 items 列表按照特定规则(第一项的利益大小)进行排序,为后续的选择操作奠定基础。
  2. 数据结构的运用:使用集合 seen 来快速判断元素的种类是否已经出现,利用列表 ll 存储重复种类的元素。
  3. 贪心算法的思想:先选择前 k 个利益最大的元素,然后通过逐步替换来尝试优化结果,体现了贪心选择局部最优以期望达到全局最优的思路。
  4. 逻辑推理和计算能力:在计算优雅度、判断是否替换元素以及更新相关变量时,需要准确的逻辑推理和计算。


学到的内容:

  1. 熟练掌握排序函数的使用,能够根据具体需求对数据进行排序。
  2. 学会运用合适的数据结构来提高算法的效率和便捷性,例如集合的快速查找和去重特性。
  3. 深入理解贪心算法的策略,以及如何在特定问题中应用贪心思想来解决优化问题。
  4. 提升了对复杂逻辑的分析和处理能力,包括条件判断、变量更新和结果优化。
  5. 培养了通过逐步推导和计算来求解最优解的思维方式,同时也学会了如何在算法中有效地管理和利用数据。

To sum up: 这道题的算法有另一个好听的名字叫 反悔贪心,难度还是在线的,多思考,多理解。 


“江流天地外,山色有无中。”——王维 

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。