数据结构和算法-贪心算法01- 认识贪心

贪心算法

image-20241030091632946

什么是贪心算法

一个贪心算法总是做出当前最好的选择,也就是说,它期望通过局部最优选择从而得到全局最优的解决方案。

​ ----《算法导论》

贪心算法(Greedy Method): 所谓贪心算法就是重复地(或贪婪地)根据一个法则挑选解的一部分。当挑选完毕时,最优解也就出现了。

贪心算法的几个核心问题

  1. 没有后悔药。一旦做出选择,不可以后悔。
  2. 有可能得到的不是最优解, 而是最优解的近似解
  3. 选择什么样的贪心策略,直接决定算法的好坏。

解决贪心算法的策略

  1. 贪心策略

    确定一个贪心策略,即选择一个好的方案。

  2. 局部最优解

    一步一步地的到局部最优解。

  3. 全局最优解

    将所有的局部最优解合成为原来问题的一个最优解。

    tips: 想想我们的冒泡排序

    image-20241030092351875

贪心算法与动态规划算法的区别

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择,不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。

再谈股票问题II

问题

[力扣122]122. 买卖股票的最佳时机 II - 力扣(LeetCode)

问题描述

给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。

在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。

返回 你能获得的 最大 利润

示例 1:

输入:prices = [7,1,5,3,6,4]
输出:7
解释:在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7

示例 2:

输入:prices = [1,2,3,4,5]
输出:4
解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
最大总利润为 4

示例 3:

输入:prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 交易无法获得正利润,所以不参与交易可以获得最大利润,最大利润为 0

解决方案

image-20241030132301012

使用贪心算法解决。

从“贪心”(获取最大利润)角度考虑,如果当天卖出的价格高于前一天买入的价格就卖出,保证利润的最大化。

image-20241030132932923
if(prices[i] > prices[i-1]){
  profits += prices[i] - prices[i-1];
}

参考实现

class Solution {
    public int maxProfit(int[] prices) {
     int profit =0;

        for (int i = 1; i < prices.length; i++) {
           if(prices[i]>prices[i-1]){
               profit+= prices[i] - prices[i-1];
           }
        }
        return profit;
    }
}

找零钱问题

问题描述

商店售货员找给 1 个顾客 n 元,用以下七种面值的纸币:100 元,50 元,20 元,10 元,5 元,2 元,1 元。

思考:如果商店售货员找给 1 个顾客 63元,假设钱币的面值有九种:100 元,50 元,20 元,10 元,5 元,2 元,1 元。用贪婪算法得到的是该问题的最优解吗?

image-20241030143038679

动态规划(DP)

image-20241031132951507

package com.ffyc.greedy;

import java.util.Arrays;

public class MoneyGreedyDp {
    public int coinChange(int[] nums, int amount) {
        int n = nums.length;
        int[] dp = new int[amount+1];

        for(int m = 1; m <=amount; m++){
            dp[m] = amount+1;
            for(int j =0; j<n;j++){
                if(nums[j] <=m ){
                    dp[m] = Math.min(dp[m],dp[m-nums[j]]+1);
                }
            }
        }
        if(dp[amount] > amount){
            return -1;
        } else{
            return dp[amount];
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 50, 2, 5, 100, 10, 20};
        int mount = 63;
        new MoneyGreedy().greedy(nums, mount);
    }
}

贪心算法

先从货币值大的开始扫描,比如先选50,则剩余13元;再选择10元,则剩余3元。采用此策略直到扫描终止。

package com.ffyc.greedy;

import java.util.Arrays;

public class MoneyGreedy {
    public void greedy(int[] nums, int amount) {
        int n = nums.length;
        //对零钱排序
        Arrays.sort(nums);
        int[] result = new int[n];

        for (int i = n-1; i >=0; i--) {
            if (amount >= nums[i]) {
                result[i] = amount / nums[i];
                amount = amount % nums[i];
            }
        }
        if(amount > 0) {
            System.out.println("剩余"+amount+"找零失败....");
            return;
        }
        System.out.println(Arrays.toString(result));
    }

    public static void main(String[] args) {
        int[] nums = {1, 50, 2, 5, 100, 10, 20};
        int mount = 63;
        new MoneyGreedy().greedy(nums, mount);
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/910674.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

创新实践:基于边缘智能+扣子的智慧婴儿监控解决方案

在2024年全国大学生物联网设计竞赛中&#xff0c;火山引擎作为支持企业&#xff0c;不仅参与了赛道的命题设计&#xff0c;还为参赛队伍提供了相关的硬件和软件支持。以边缘智能和扣子的联合应用为核心&#xff0c;参赛者们在这场竞赛中的方案展现出了卓越的创新性和实用性&…

6款IntelliJ IDEA插件,让Spring和Java开发如虎添翼

文章目录 1、SonarLint2、JRebel for IntelliJ3、SwaggerHub插件4、Lombok插件5、RestfulTool插件6、 Json2Pojo插件7、结论 对于任何Spring Boot开发者来说&#xff0c;两个首要的目标是最大限度地提高工作效率和确保高质量代码。IntelliJ IDEA 是目前最广泛使用的集成开发环境…

CSS弹性布局:灵活布局的终极指南

在网页设计中&#xff0c;CSS 弹性布局&#xff08;Flexbox&#xff09;是一个不可或缺的工具。它能帮助你轻松地排列和对齐元素&#xff0c;尤其是在响应式设计中表现出色。今天&#xff0c;我们就来深入探讨一下 Flexbox 的各个属性&#xff0c;让你彻底掌握这个强大的布局工…

论文阅读:Computational Long Exposure Mobile Photography (一)

这篇文章是谷歌发表在 2023 ACM transaction on Graphic 上的一篇文章&#xff0c;介绍如何在手机摄影中实现长曝光的一些拍摄效果。 Abstract 长曝光摄影能拍出令人惊叹的影像&#xff0c;用运动模糊来呈现场景中的移动元素。它通常有两种模式&#xff0c;分别产生前景模糊或…

CTF入门教程(非常详细)从零基础入门到竞赛,看这一篇就够了!

目录 一、CTF简介 二、CTF竞赛模式 三、CTF各大题型简介 四、CTF学习路线 4.1、初期 1、htmlcssjs&#xff08;2-3天&#xff09; 2、apachephp &#xff08;4-5天&#xff09; 3、mysql &#xff08;2-3天&#xff09; 4、python (2-3天) 5、burpsuite &#xff08;…

linux 进程调度学习笔记

https://zhuanlan.zhihu.com/p/1248579228 吐血整理 | 肝翻 Linux 进程调度所有知识点 执行调度 Kernel 判断当前进程标记是否为 TIF_NEED_RESCHED&#xff0c;是的话调用 schedule 函数&#xff0c;执行调度&#xff0c;切换上下文&#xff0c;这也是上面抢占(preempt)机制的…

django图书管理系统-计算机毕业设计源码00648

摘要 图书管理系统在数字化阅读趋势、图书馆自动化管理、用户体验需求和信息技术应用等方面具有重要的研究意义。图书馆自动化管理系统的引入和应用提高了图书借阅过程的效率和准确性&#xff0c;减少了对手工操作和纸质记录的需求。用户对系统的易用性、查询速度、借还流程有更…

SQL实战训练之,力扣:2020. 无流量的帐户数(递归)

目录 一、力扣原题链接 二、题目描述 三、建表语句 四、题目分析 五、SQL解答 六、最终答案 七、验证 八、知识点 一、力扣原题链接 2020. 无流量的帐户数 二、题目描述 表: Subscriptions ------------------- | Column Name | Type | ------------------- | accoun…

ARM base instruction -- ccmp (immediate)

Conditional Compare (immediate) sets the value of the condition flags to the result of the comparison of a register value and an immediate value if the condition is TRUE, and an immediate value otherwise. 此指令一般出现在 cmp 指令之后&#xff0c;表示双重比…

【支付行业-支付系统架构及总结】

记得第一次看埃隆马斯克&#xff08;Elon Musk&#xff09;讲第一性原理的视频时&#xff0c;深受震撼&#xff0c;原来还可以这样处理复杂的事务。这篇文章也尝试化繁为简&#xff0c;探寻支付系统的本质&#xff0c;讲清楚在线支付系统最核心的一些概念和设计理念。 虽然支付…

【系统面试篇】进程和线程类(1)(笔记)——区别、通讯方式、同步、互斥、锁分类

目录 一、问题综述 1. 进程和线程的区别&#xff1f; 2. 进程的状态有哪些&#xff1f; 3. 进程之间的通信方式? &#xff08;1&#xff09;管道 &#xff08;2&#xff09;消息队列 &#xff08;3&#xff09;共享内存 &#xff08;4&#xff09;信号量 &#xff08…

Java算法OJ(6)归并分治

目录 1.前言 2.正文 2.1归并分治的概念 2.2计算数组的小和 2.2.1题目 2.2.2示例 2.2.3代码 2.3翻转对 2.3.1题目 2.3.2示例 2.3.3代码 3.小结 1.前言 哈喽大家好吖&#xff0c;今天继续来给大家带来Java算法——归并分治的讲解&#xff0c;学习这篇的前提可以先把…

【网络】自定义协议——序列化和反序列化

> 作者&#xff1a;დ旧言~ > 座右铭&#xff1a;松树千年终是朽&#xff0c;槿花一日自为荣。 > 目标&#xff1a;了解什么是序列化和分序列&#xff0c;并且自己能手撕网络版的计算器。 > 毒鸡汤&#xff1a;有些事情&#xff0c;总是不明白&#xff0c;所以我不…

Abaqus随机骨料过渡区孔隙三维网格插件:Random Agg ITZ Pore 3D (Mesh)

插件介绍 Random Agg ITZ Pore 3D (Mesh) V1.0 - AbyssFish 插件可在Abaqus内参数化建立包含水泥浆基体、粗细骨料、界面过渡区&#xff08;ITZ&#xff09;、孔隙在内的多相材料混凝土细观背景网格模型。 模型说明 插件采用材料映射单元的方式&#xff0c;将不同相材料赋值…

【含开题报告+文档+源码】基于SpringBoot+Vue智能居民健康检测系统设计与实现

开题报告 随着社会发展和人民生活水平的提高&#xff0c;人们对健康生活的要求越来越高。而广大居民由于条件限制&#xff0c;存在着健康管理服务不足的问题。本文基于JavaWeb技术&#xff0c;设计并实现了一种居民健康检测系统。首先&#xff0c;本文对该平台的需求进行了分析…

基于Multisim8路抢答器电路仿真电路(含仿真和报告)

【全套资料.zip】8路抢答器电路仿真电路Multisim仿真设计数字电子技术 文章目录 功能一、Multisim仿真源文件二、原理文档报告资料下载【Multisim仿真报告讲解视频.zip】 功能 1.设计数字式抢答器&#xff0c;每组选手具有一个抢答按钮。 2.电路具有第一抢答信号的鉴别和锁存…

Java 网络编程(一)—— UDP数据报套接字编程

概念 在网络编程中主要的对象有两个&#xff1a;客户端和服务器。客户端是提供请求的&#xff0c;归用户使用&#xff0c;发送的请求会被服务器接收&#xff0c;服务器根据请求做出响应&#xff0c;然后再将响应的数据包返回给客户端。 作为程序员&#xff0c;我们主要关心应…

人工智能学习--归一化(Normalization)

概念 归一化是数据预处理中将不同量纲的特征数据缩放至同一尺度的过程&#xff0c;使特征值落在同一范围&#xff08;如[0, 1]或[-1, 1]&#xff09;。归一化有助于消除量纲影响&#xff0c;提升算法的收敛速度和模型稳定性&#xff0c;尤其在梯度下降和距离计算等算法中尤为重…

高校实验室安全巡检系统设计与实现(源码+定制+开发)高校实验室巡检系统、实验室安全管理平台、实验室安全监控系统、智能实验室巡查系统、高校实验室风险管理

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…

解决程序因缺少xinput1_3.dll无法运行的有效方法,有效修复丢失xinput1_3.dll

如果你的电脑在运行某些应用程序或游戏时提示“xinput1_3.dll丢失”或“找不到xinput1_3.dll”的错误消息&#xff0c;那么很可能是因为你的系统中缺少这个重要的DLL文件而导致的问题。那么电脑出现xinput1_3.dll丢失的问题时有哪些方法进行修复呢&#xff1f; 如何确定电脑是否…