贪心法——活动选择问题和背包问题

简介:         今天上午听了米老师讲的算法,感觉收获很多,对于算法更加有信心了。首先,先来宏观看一下:                      这三种算法总的来说,刚开始看的时候不知道怎么下手,但是看多了也会有那么一点儿感觉。



        今天上午听了米老师讲的算法,感觉收获很多,对于算法更加有信心了。首先,先来宏观看一下:

 

       




           这三种算法总的来说,刚开始看的时候不知道怎么下手,但是看多了也会有那么一点儿感觉。分治法是这三种算法里面都有的思想,动态规划和贪心都是将问题分解成子问题求解,但动态规划里面的子问题都带有联系,而贪心算法里面的子问题都相对独立,唯一不同的是,贪心算法要首先想出一个解决方案来构造求解最优解的过程。


     宏观介绍下算法后,来看看贪心算法的两个实例。


   一,活动选择问题


    

          


    解决方案:   

              对于活动的选择问题,我们求解过程是这样的,先把这些活动按照结束时间从早到晚排列,然后从第一个开始选择,如果第i个活动的开始时间比第i-1个活动的结束时间晚,我们就将此活动加入到解集合中。


       

    伪代码解读:



          递归方式求解:


   




            迭代方式求解:





   如果看完伪代码后还是没什么感觉,可以用下面的一些数据进行计算:

          


    



二,背包问题

 

       



   解决方案:


           因为可以部分装入背包,所以,我们将物品按照单位价值从大到小排序,依次选取,直到背包被装满为止。


 伪代码解读:


        


 


      

       小结,本来也想写写动态规划的伪代码注解的,but......我也不太懂,算法一直以来是我比较弱的地方,但是感觉研究起来,也是最有意思的,跪求大神参与讨论~~~~~~~

       

  



目录
相关文章
|
机器学习/深度学习 算法 程序员
C++ Algorithm 库 算法秘境探索(Algorithm Wonderland Exploration)
C++ Algorithm 库 算法秘境探索(Algorithm Wonderland Exploration)
480 1
|
传感器 机器学习/深度学习 数据采集
【航迹关联】基于NNDA、PDA、JPDA三种算法实现航迹关联附matlab代码
【航迹关联】基于NNDA、PDA、JPDA三种算法实现航迹关联附matlab代码
|
7月前
|
数据采集 JSON 数据可视化
JSON数据解析实战:从嵌套结构到结构化表格
在信息爆炸的时代,从杂乱数据中提取精准知识图谱是数据侦探的挑战。本文以Google Scholar为例,解析嵌套JSON数据,提取文献信息并转换为结构化表格,通过Graphviz制作技术关系图谱,揭示文献间的隐秘联系。代码涵盖代理IP、请求头设置、JSON解析及可视化,提供完整实战案例。
432 4
JSON数据解析实战:从嵌套结构到结构化表格
|
XML 设计模式 存储
Java Spring IOC容器与依赖注入DI实现原理
本文主要讲解Spring IOC机制和实现过程,依赖注入DI和面向切面编程AOP是Spring框架的核心概念,几乎后续使用到Spring Boot框架的地方都有这两个概念的影子。也是Java面试的考察点,我们会结合实际的例子演示说明 。
|
11月前
|
数据可视化 前端开发 UED
低代码可视化-Uniapp Cascader级联选择器-代码生成器
Cascader级联选择器是一种常用的UI组件,适用于从具有层级关系的数据中进行选择,如省市区选择、公司层级选择等。它通过分组多列展示选项,支持多级分类、联动选择、搜索与过滤等功能。组件具备自定义样式、禁用选项、清空选项等特性,广泛应用于电商、企业内部系统等场景。代码示例展示了其详细的实现和调用方法。
437 7
低代码可视化-Uniapp Cascader级联选择器-代码生成器
|
SQL API 数据库
为API设置默认排序规则结果数据的正确性
Dataphin数据服务支持API调用时通过OrderByList自定义排序,确保数据返回符合业务需求。默认排序在API设计时至关重要,因为它影响用户体验、数据一致性及查询正确性。新版本 Dataphin 提供了排序优先级设置,允许在SQL脚本或OrderByList中指定排序,以适应不同场景。
221 0
|
前端开发 容器
css溢出隐藏的五种方法
css溢出隐藏的五种方法
252 1
|
XML Java API
Spring Boot快速入门指南
Spring Boot快速入门指南
|
存储 SQL NoSQL
数据库基础教程
数据库基础教程
|
编解码 人工智能 大数据
久等了!阿里云开发者社区APP服务上线啦!
阿里云开发者社区APP服务上线啦!本文将为大家介绍APP服务中不可错过的亮点及下载地址。
3215 4
久等了!阿里云开发者社区APP服务上线啦!