算法学习--贪心

简介: 算法学习--贪心

交换邻项得到序列


这一类题目一般都是牵扯到顺序的, AB 和 BA 得到的价值是不一样的, 这个时候就会通过研究局部最优解来得到一个全局最优解, 如果原来是 AB, 在某种条件 Cond 下, BA 的价值更大, 那么就交换 AB 的顺序变成 BA, 我们也就可以使用条件 Cond 来对整个序列进行排序


125. 耍杂技的牛 - AcWing 题库


这道题目, 我们考虑第 i 头牛和第 i+1 头牛交换前和交换后的风险值


交换前 交换后
i C-s[i] C-s[i+1]
i+1 C+w[i]-s[i+1] C+w[i+1]-s[i]


我们可以发现 C+wi−si+1 一定 大于 C−Si+1 , C+wi+1−si一定大于 C−si, 所以这四个数的最大值一定出自 C+wi−si+1C+wi+1−si

wi+1−si<wi−si+1时, 也就是 wi+1+si+1<wi+si, 综合以上分析, 交换才会是风险值的最大值变小, 重载 bool operator<() 返回 false 发生交换, 把每头牛按照 w+s 来从小到大排序得到的序列, 其风险值的最大值最小


#include<iostream>
#include<algorithm>
using namespace std;
const int NN=50010;
struct Cow{
    int w,s;
    bool operator<(Cow& c){
        return w+s<c.w+c.s;
    }
}cow[NN];
int n;
// 贪心策略 研究相邻两项的交换来确定整体排序
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int w,s;
        scanf("%d%d", &w, &s);
        cow[i]={w, s};
    }
    sort(cow, cow+n);
    int danger=-2e9;
    int w_s=0;
    for(int i=0;i<n;i++){
        danger=max(danger, w_s-cow[i].s);
        w_s+=cow[i].w;
    }
    cout<<danger<<endl;
    return 0;
}


734. 能量石 - AcWing 题库

在这道题目当中, 需要考虑的问题有:

  1. 选择哪些能量石
  2. 以什么样的顺序吃选到的能量石

我们可以先考虑所有能量石, 找到一个最合适的拓扑序列, 这样就把能量石的食用循序确定了下来( 这是交换相邻项得序列问题 ), 之后再从这个序列中选中最优一个子序列 ( 这是一个 01 背包问题 ), 进一步把吃那些能量石也确定了下来


获得的能量
交换前 E'[i]+E'[i+1]-S[i]*L[i+1]
交换后 E'[i]+E'[i+1]-S[i+1]*L[i]


当满足 E'[i]+E'[i+1]-S[i+1]*L[i] > E'[i]+E'[i+1]-S[i]*L[i+1] 时, 也就是 S[i+1]*L[i] < S[i]*L[i+1] 时, 交换可以使得到的能量变大, bool operator<() 返回 false


#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int NN=110, MM=10010;
int T, N;
struct Stone{
    int s,e,l;
    bool operator<(Stone& rhs){
        if(rhs.s*l<s*rhs.l)
            return false;
        return true;
    }
}stone[NN];
int f[MM]; // f[j] 表示时间点恰好为 j 时, 获得能量的最大值, 因为这道题目需要精确的时间点来计算能量石的价值
int main(){
    cin>>T;
    for(int idx=1;idx<=T;idx++){
        memset(f, -0x3f, sizeof f);
        f[0]=0;
        cin>>N;
        for(int i=1;i<=N;i++){
            int s, e, l;
            scanf("%d%d%d", &s, &e, &l);
            stone[i]={s,e,l};
        }
        sort(stone+1, stone+1+N);
        for(int i=1;i<=N;i++){
            for(int j=MM-1;j>=stone[i].s;j--){
                int si=stone[i].s, ei=stone[i].e, li=stone[i].l;
                f[j]=max(f[j], f[j-si]+max(0, ei-(j-si)*li));
            }
        }
        int res=0;
        for(int i=0;i<MM;i++){
            res=max(res, f[i]);
        }
        printf("Case #%d: %d\n", idx, res);
    }
}


关于背包问题的初始化问题

  1. 求方案数的初始化
  • 体积至多 j,f[i] = 1, 0 <= i <= m,
  • 体积恰好 j,f[0] = 1, 其余是 0
  • 体积至少 j,f[0] = 1,其余是 0
  1. 求最值的初始化
  • 体积至多j,f[i] = 0, 0 <= i <= m
  • 体积恰好j,
  • 当求价值的最小值:f[0] = 0, 其余是INF
  • 当求价值的最大值:f[0] = 0, 其余是-INF
  • 体积至少j,f[0] = 0,其余是INF

当体积至多为 j 的时候, 初始状态的所有 f[i] 都可以有 f[0] 转移过去, 所以 f[i]=f[0]

相关文章
|
2月前
|
存储 算法 Go
算法学习:数组 vs 链表
算法学习:数组 vs 链表
36 0
|
2月前
|
机器学习/深度学习 算法 PyTorch
【从零开始学习深度学习】43. 算法优化之Adam算法【RMSProp算法与动量法的结合】介绍及其Pytorch实现
【从零开始学习深度学习】43. 算法优化之Adam算法【RMSProp算法与动量法的结合】介绍及其Pytorch实现
|
11天前
|
机器学习/深度学习 人工智能 资源调度
【博士每天一篇文献-算法】连续学习算法之HAT: Overcoming catastrophic forgetting with hard attention to the task
本文介绍了一种名为Hard Attention to the Task (HAT)的连续学习算法,通过学习几乎二值的注意力向量来克服灾难性遗忘问题,同时不影响当前任务的学习,并通过实验验证了其在减少遗忘方面的有效性。
28 12
|
4天前
|
算法 Java
掌握算法学习之字符串经典用法
文章总结了字符串在算法领域的经典用法,特别是通过双指针法来实现字符串的反转操作,并提供了LeetCode上相关题目的Java代码实现,强调了掌握这些技巧对于提升算法思维的重要性。
|
6天前
|
算法 NoSQL 中间件
go语言后端开发学习(六) ——基于雪花算法生成用户ID
本文介绍了分布式ID生成中的Snowflake(雪花)算法。为解决用户ID安全性与唯一性问题,Snowflake算法生成的ID具备全局唯一性、递增性、高可用性和高性能性等特点。64位ID由符号位(固定为0)、41位时间戳、10位标识位(含数据中心与机器ID)及12位序列号组成。面对ID重复风险,可通过预分配、动态或统一分配标识位解决。Go语言实现示例展示了如何使用第三方包`sonyflake`生成ID,确保不同节点产生的ID始终唯一。
go语言后端开发学习(六) ——基于雪花算法生成用户ID
|
11天前
|
存储 机器学习/深度学习 算法
【博士每天一篇文献-算法】连续学习算法之HNet:Continual learning with hypernetworks
本文提出了一种基于任务条件超网络(Hypernetworks)的持续学习模型,通过超网络生成目标网络权重并结合正则化技术减少灾难性遗忘,实现有效的任务顺序学习与长期记忆保持。
14 4
|
11天前
|
存储 机器学习/深度学习 算法
【博士每天一篇文献-算法】连续学习算法之RWalk:Riemannian Walk for Incremental Learning Understanding
RWalk算法是一种增量学习框架,通过结合EWC++和修改版的Path Integral算法,并采用不同的采样策略存储先前任务的代表性子集,以量化和平衡遗忘和固执,实现在学习新任务的同时保留旧任务的知识。
49 3
|
12天前
|
存储 机器学习/深度学习 算法
【博士每天一篇文献-综述】基于脑启发的连续学习算法有哪些?附思维导图
这篇博客文章总结了连续学习的分类,包括经典方法(重放、正则化和稀疏化方法)和脑启发方法(突触启发、双系统启发、睡眠启发和模块化启发方法),并讨论了它们在解决灾难性遗忘问题上的优势和局限性。
13 2
|
1月前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
|
1月前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战

热门文章

最新文章