算法与数据结构高手养成:朴素的贪心法(上)最优化策略

简介: 算法与数据结构高手养成:朴素的贪心法(上)最优化策略

朴素的贪心法(上)最优化策略

常见贪心法归类

1.最优化策略——每一次都采用当前最优决策

2.构造法——通过总结和归纳找到规律,直接推导出答案

3.二分答案——通过答案反推,验证合法性从而确定最优解

何为“朴素”贪心

  • 所谓“朴素”,就是可以通过确定性的贪心步骤得出最优解
  • 有些问题很难通过确定性贪心步骤得到最优解,但可以通过在贪心时加入随机因素(不是每次都选最优策略,而是几种较好策略中随机选择一种),来得到近似最优解
  • 当随机次数足够多时,这个近似最优解就会无限逼近最优解这个方法称为随机贪心法,后续会

最优化策略:取石子

每次都选取最大~

取石子(改)

由于条件限制,不能做到每次都拿最多,如果第一次拿3,第二次拿4时,第三次就不能再拿了

不适用贪心,但动态规划可解

最优化策略适用条件

第一,有明确的阶段,且每个阶段的决策都很清晰

  • 阶段一定是按顺序执行的
  • 对于第K(1≤K≤N)个阶段,前K轮的最优决策集合称为局部最优解当K=N时,称为全局最优解

第二,一个阶段的局部最优解,一定是从前面阶段的局部最优解得到的,这个特性称之为最优子结构

  • 例:取石子里,第二轮如果取4,那么无论第三轮取什么,总数一定不是最多。只有第二轮取5(局部最优解)第三轮才有可能产生总数最多的情况
  • 反例:取石子(改)里,第二轮取5是当前最优,但第三轮取4是最优。只有第二轮不取当前最优时,第三轮才能取到最优——不适用贪心法

第三,后面阶段的决策,不会影响到前面阶段的决策,这个特性称为无后效性

  • 例:无论第二轮取哪一堆,都不影响第一轮取的石子
  • 反例:题目修改为“每种数目的石子只能取一次,比如这一次取了5个,下一次就不能再取5个”——后面选择跟前面冲突的话,就需要返回修改之前的选择

最优化策略:分析步骤

1.划分问题的阶段决策

2.验证最优子结构无后效性

3.通过比较和判断,确定每一步的最优策略

例题:机器工厂(USACO)

步骤1:划分阶段和决策

  • 阶段:周数 K(1 ≤K≤ N)
  • 决策:第 K周生产多少台机器

步骤2:验证最优子结构/无后效性

  • 无后效性:满足
  • 因为第 K 周生产几台都不影响第1~K-1周的交付(不可能后面生产的穿越回去交付前面的订单)
  • 最优子结构呢?

局部最优解定义:完成前 K周订单的总成本最小(K=N)时就是全局最优解 在这个定义下,局部最优解一定是刚好满足K周订单需求即可不会额外生产供以后交付,否则会浪费

不满足最优子结构?

步骤2.5:修改决策

  • 问题出在决策:不能只满足本周的需求而不考虑后续需要
  • 反向思考1:本周要交付的机器可以是本周生产,也可以是之前生产
  • 反向思考2:不管前面是哪周生产,成本都可以直接算出来(等于该周生产成本+储藏成本x周数差)

例:前三周每个机器生产成本分别是1,5,6,储藏成本是2

第三周要交付的机器如果在当周生产,成本是6,如果要在第二周生产,成本是5+2x1=7;如果要在第一周生产,成本是1+2x2=5

所以,第三周交付的机器,在第一周生产最省钱

步骤2.5:重新验证最优子结构/无后效性

  • 决策修改为:第K周要交付的机器应该在第几周生产
  • 无后效性仍然满足
  • 最优子结构也满足:前K周总成本最低的情况,一定是从前K-1周总成本最低的情况推出来的

步骤3:最优化策略

  • 对于第K周,计算本周交付的机器在第i(1≤i≤K)周生产并储藏到第K周,分别所需要的成本
  • 选择成本最低的一周,由它来生产第K周需要交付的订单
  • 将这个最低的成本加上前K-1周的最低总成本,得到前K周的最低总成本(局部最优解)。K=N时得到的就是最终答案

虽然问题解决了,但是这个方法的效率还有提升空间

决策时,选择某一成本最低的一周的时候,我们刚刚采用的策略是挨个计算出每一周的成本,从而选择最小的,涉及了很多重复计算,成本的变化是有一定规律的,并不需要每次都进行计算~

步骤3:最优化策略(改进)

直接把时间复杂度降低了一个数量级~时间复杂度对O(n)

代码:机器工厂(C++)

    int n, s; // 声明变量n和s,分别表示总共的星期数和保养一台机器的费用
    cin >> n >> s; // 输入总星期数和保养费用
    int p, y, min_p = INT_MAX - s; // 声明变量p、y和min_p,min_p初始化为INT_MAX-s,用来存放当前最小的生产成本
    long long total = 0; // 声明变量total用来存放总花费
    for (int i = 0 ;i < n; i++) // 循环n次,表示n个星期
    {
        cin >> p >> y; // 输入当前星期生产一台机器的成本p和订单数量y
        min_p = min(min_p + s, p); // 对当前最小成本进行更新,考虑了保养费用
        total += min_p * y; // 计算当前星期的总花费,加上当前最小成本乘以订单数量
    }
    cout << total << endl; // 输出总花费
 
    return 0;

希望对你有帮助!加油!

若您认为本文内容有益,请不吝赐予赞同并订阅,以便持续接收有价值的信息。衷心感谢您的关注和支持!

目录
相关文章
|
8天前
|
缓存 算法 Java
本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制
在现代软件开发中,性能优化至关重要。本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制。通过调整垃圾回收器参数、优化堆大小与布局、使用对象池和缓存技术,开发者可显著提升应用性能和稳定性。
30 6
|
10天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
11天前
|
人工智能 算法 大数据
Linux内核中的调度算法演变:从O(1)到CFS的优化之旅###
本文深入探讨了Linux操作系统内核中进程调度算法的发展历程,聚焦于O(1)调度器向完全公平调度器(CFS)的转变。不同于传统摘要对研究背景、方法、结果和结论的概述,本文创新性地采用“技术演进时间线”的形式,简明扼要地勾勒出这一转变背后的关键技术里程碑,旨在为读者提供一个清晰的历史脉络,引领其深入了解Linux调度机制的革新之路。 ###
|
21天前
|
人工智能 算法 数据安全/隐私保护
基于遗传优化的SVD水印嵌入提取算法matlab仿真
该算法基于遗传优化的SVD水印嵌入与提取技术,通过遗传算法优化水印嵌入参数,提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试,展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化,有效提升了水印技术的应用价值。
|
20天前
|
存储 缓存 算法
优化轮询算法以提高资源分配的效率
【10月更文挑战第13天】通过以上这些优化措施,可以在一定程度上提高轮询算法的资源分配效率,使其更好地适应不同的应用场景和需求。但需要注意的是,优化策略的选择和实施需要根据具体情况进行详细的分析和评估,以确保优化效果的最大化。
|
21天前
|
并行计算 算法 IDE
【灵码助力Cuda算法分析】分析共享内存的矩阵乘法优化
本文介绍了如何利用通义灵码在Visual Studio 2022中对基于CUDA的共享内存矩阵乘法优化代码进行深入分析。文章从整体程序结构入手,逐步深入到线程调度、矩阵分块、循环展开等关键细节,最后通过带入具体值的方式进一步解析复杂循环逻辑,展示了通义灵码在辅助理解和优化CUDA编程中的强大功能。
|
22天前
|
存储 缓存 算法
前端算法:优化与实战技巧的深度探索
【10月更文挑战第21天】前端算法:优化与实战技巧的深度探索
19 1
|
24天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
9天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
11天前
|
存储 算法 决策智能
基于免疫算法的TSP问题求解matlab仿真
旅行商问题(TSP)是一个经典的组合优化问题,目标是寻找经过每个城市恰好一次并返回起点的最短回路。本文介绍了一种基于免疫算法(IA)的解决方案,该算法模拟生物免疫系统的运作机制,通过克隆选择、变异和免疫记忆等步骤,有效解决了TSP问题。程序使用MATLAB 2022a版本运行,展示了良好的优化效果。