首页 > 编程语言 >贪心算法

贪心算法

时间:2023-05-13 14:02:38浏览次数:47  
标签:硬币 点此 算法 跳转 最优 贪心

原文点此跳转

介绍

贪心算法是算法设计的一种方法。期盼通过每个阶段的局部最优选择,从而达到全局的最优。但结果不一定是最优的。


基础案例

场景一

零钱兑换

现有硬币 1 元、2 元、5 元,需要用最少的硬币数量凑够 11 元。

利用贪心算法实现,优先考虑最好的结果就是面值为 5 元的硬币,11 = 5 + 5 + 1,一共使用了三枚硬币。

现有硬币 1 元、3 元、4 元,需要用最少的硬币数量凑够 5 元。

利用贪心算法实现,优先考虑最好的结果就是面值为 4 元的硬币,6 = 4 + 1 + 1,一共用了三枚硬币,虽然结果是对的,但是并不是最优的,因为用两枚 3 元硬币才是最优。

原文点此跳转


标签:硬币,点此,算法,跳转,最优,贪心
From: https://blog.51cto.com/u_12639291/6273689

相关文章

  • 什么是回溯算法
    原文点此跳转介绍回溯算法是算法设计中的一种方法。回溯算法是一种渐进式寻找并构建问题解决方式的策略。回溯算法会先从一个可能的动作开始解决问题,如果不行,就回溯并选择另一个动作,直到将问题解决。就像你在一个迷宫里面遇到了当前有三条岔路,你选择了第一条后发现此路不通,那你是不......
  • 常见算法
    寻路深度四个方向,依次寻找,入栈,都走完了就出栈回退1#include<iostream>2usingnamespacestd;34#include<graphics.h>56#include"MyStack.h"78//格子宽高9#defineSPACE80101112//Y竖着13#defin......
  • 异常检测专栏(三)传统的异常检测算法——上
    前言在上一篇推文中,我们简要介绍了异常检测常用的几种数据集如ImageNet、CIFAR10/CIFAR100、MNIST等。接下来,我们将基于传统的异常检测算法分为上、下两部分,逐一介绍不同类别的方法。本教程禁止转载。同时,本教程来自知识星球【CV技术指南】更多技术教程,可加入星球学习。欢迎关注......
  • 西门子S7-1200PLC双轴定位算法电池焊接控制博图程序 案例,触摸屏画面采用威纶触摸屏。
    西门子S7-1200PLC双轴定位算法电池焊接控制博图程序案例,触摸屏画面采用威纶触摸屏。程序设计结构灵活,采用SCL语言+梯形图结构,项目包括:1.博图V15PLC程序2.威纶通触摸屏程序3.电气施工图纸(PDF版本)4.电气采购BOM清单5.DI/DO定义表ID:31156755198......
  • 文心一言 VS chatgpt (16)-- 算法导论4.1 1~2题
    一、当A的所有元素均为负数时,FIND-MAXIMUM-SUBARRAY返回什么?文心一言:当A的所有元素均为负数时,FIND-MAXIMUM-SUBARRAY返回-1。这是因为在二进制中,当所有元素均为负数时,A的每个元素都对应一个负数,而-1的二进制表示是11111111,与A的每个元素的值的每一位的负号是相对应的,所以,如果F......
  • 算法训练DAY01
    算法训练DAY01|704.二分查找、27.移除元素704.二分查找大体思路:处理数组为空的特殊情况初始化left,right,使用[l,r]形式的二分法确定while条件,处理二分实现细节:(l+r)//2python中//运算符向下取整处理while中的分支时,最好用continue跳出循环,少用ifelse27.移除元素......
  • 精选论文 | Capon算法与MUSIC算法性能的比较与分析
    公众号【调皮连续波】,其他平台为自动同步,内容若不全或乱码,请前往公众号阅读。持续关注调皮哥,获得更多雷达干货学习资料和建议,和大家一起学习雷达技术。【正文】首先说结论:当信噪比(SNR)足够大时,Capon算法和MUSIC算法的空间谱非常相似,因此在SNR比较大时它们的性能几乎一样,当不同信号源......
  • m基于图像灰度共生矩阵纹理提取和GRNN神经网络的人口密度检测算法matlab仿真
    1.算法仿真效果matlab2013b仿真结果如下:  2.算法涉及理论知识概要       灰度共生矩阵,指的是一种通过研究灰度的空间相关特性来描述纹理的常用方法。[1] 1973年Haralick等人提出了用灰度共生矩阵来描述纹理特征。由于纹理是由灰度分布在空间位置上反复出现而形......
  • 代码随想录算法训练营第三天|203.移除链表元素 、707.设计链表 、206.反转链表
    一.链表基础1.最后一个节点的指针域指向null(空指针的意思)。2.链表在内存中不是连续分布的。3.链表的长度可以是不固定的,并且可以动态增删,适合数据量不固定,频繁增删,较少查询的场景。1#链表节点的定义2classListNode:3def__init__(self,val,next=None):4......
  • m基于HOG特征提取和GA优化GRNN网络的交通标志检测和识别算法matlab仿真
    1.算法仿真效果matlab2022a仿真结果如下:       2.算法涉及理论知识概要2.1遗传算法       遗传算法GA把问题的解表示成“染色体”,在算法中也即是以二进制编码的串。并且,在执行遗传算法之前,给出一群“染色体”,也即是假设解。然后,把这些假设解置于......