算法学习——贪心算法之币种统计

2023-11-20

算法描述

币种统计

单位给每一位员工发工资(精确到元),为了保证不临时换零钱,使得每个员工取款的张数最少,在取工资前统计所有员工所需要的各种票面的张数(约定票种为100,50,20,10,5,2,1元),并验证币种统计是否正确

算法思路

  1. 算法描述其实是省略了要求,用户肯定是要输入员工数以及各位员工的工资

    定义:n位员工,G[n]对应了第n员工的工资

  2. a数组存放100元到1元的面值,a[0]=100,a[1]=50...

  3. b数组对应每个面值的张数,b[0]对应100元的张数,b[1]对应50元的张数...

  4. 采用贪心策略,每次取最大面值

算法实现

    System.out.println("输入员工数n:");
    Scanner scanner = new Scanner(System.in);
    int n=scanner.nextInt();
    
    System.out.println("依次输入员工的工资");
    int[] G = new int[n];
    for(int i=0;i<n;i++){
        G[i]=scanner.nextInt();
    }
    scanner.close();

    int sumG = 0;//计算全体员工工资总和,便于之后的验证
    int sum = 0;
    for(int i=0;i<G.length;i++){
        sumG = sumG + G[i];
    }
    
    int[] a = {100,50,20,10,5,2,1};//7个面值不同币种
    int[] b = new int[7];//存放个面值对应的张数
    boolean flag = true;
    
    for(int i=0;i<G.length;i++){
        for(int j=0;j<a.length;j++){
            while(G[i]>=a[j]){//每次取最大面值
                G[i]=G[i]-a[j];
                b[j]++;//当前面值对应的张数+1
            }
        }
    }
    //显示各面值对应需要的张数
    for(int i=0;i<b.length;i++){
        System.out.println("需要"+b[i]+"张面值为"+a[i]+"元的纸币");
        sum = sum+b[i]*a[i];
    }
    
    //验证,各个面值与其对应的张数想乘的总和等于全部员工工资的总和,则说明算法正确
    if(sumG==sum){
        System.out.println("该算法正确!");
    }

结果

1210268-20181027171106223-1727877162.png

转载于:https://www.cnblogs.com/kexing/p/9862350.html

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

算法学习——贪心算法之币种统计 的相关文章

  • 数据库多维迭代算法

    关键词 数据库 迭代 递归 多维 一 两种传统的数据库迭代结构算法 对于数据库的迭代结构 有两种传统的算法 递归算法和边界算法 比如对于下面图1的结构 图1 递归算法的数据结构如表1所示 节点id 节点值 父节点id 1 1111 2 3
  • 《Linux From Scratch》第三部分:构建LFS系统 第六章:安装基本的系统软件- 6.29. Coreutils-8.23...

    Coreutils 软件包包含用于显示和设置基本系统特性的工具 大概编译时间 2 5 SBU 需要磁盘空间 193 MB 6 29 1 安装 Coreutils POSIX 要求 Coreutils 中的程序即使在多字节语言环境也能正确识别
  • 一文弄懂循环链表、双向链表、静态链表

    循环链表 双向链表 静态链表 三遍定律 理解了单链表本文的理解易如反掌 单链表请点击这里 理解了单链表本文的理解易如反掌 单链表请点击这里 理解了单链表本文的理解易如反掌 单链表请点击这里 1 循环链表 将单链表中终端结点的指针端由空指针改
  • Qt——用于表格QTableView的模型

    如果想使用表格来呈现数据 Qt提供了一个方便的部件QTableWidget 但是直接用它实现一些功能可能比较困难 这里将介绍一种强大 灵活的方式来操作表格 一 模型 视图架构 在这个架构中 模型用于存储数据 视图用于呈现数据 除此之外 还有
  • 微软2013暑假实习生笔试题

    自己mark一下 以作后备 下面提交原文链接 原文博客 部分题目答案不确定 会持续更新 1 Which of the following calling convention s support s supportvariable leng
  • 以太坊系列之十五: 以太坊数据库

    以太坊数据库中都存了什么 以太坊使用的数据库是一个NOSQL数据库 是谷歌提供的开源数据leveldb 这里尝试通过分析以太坊数据库存储了什么来分析以太坊可能为我们提供哪些关于区块链的API 存储内容 NOSQL是一个key value数据
  • 字符串09--表示数值的字符串

    字符串09 表示数值的字符串 jz53 题目概述 解析 参考答案 注意事项 说明 题目概述 算法说明 请实现一个函数用来判断字符串是否表示数值 包括整数和小数 例如 字符串 100 5e2 123 3 1416 和 1E 16 都表示数值
  • 数据结构——计算节点个数和二叉树高度(C语言版)

    摘自 数据结构 计算节点个数和二叉树高度 C语言版 作者 正弦定理 发布时间 2020 12 12 23 27 09 网址 https blog csdn net chinesekobe article details 111086664
  • 如何防止过拟合和欠拟合

    过拟合和欠拟合是模型训练过程中经常出现的问题 两种情况正好相反 现将两者的定义及如何防止进行简要总结 1 过拟合 1 1 定义 是指模型对于训练数据拟合呈现过当的情况 反映到评估指标上就是模型在训练集上的表现很好 但是在测试集上的表现较差
  • 算法问题实战策略

    算法问题实战策略 基本信息作者 韩 具宗万 译者 崔盛一出版社 人民邮电出版社ISBN 9787115384621上架时间 2015 2 4出版日期 2015 年3月开本 16开页码 738版次 1 1 内容简介 算法问题实战策略 本书收录
  • OJ-合并两个有序链表

    题目描述 代码如下 Definition for singly linked list struct ListNode int val struct ListNode next struct ListNode mergeTwoLists s
  • Linux下进程退出的几种形式

    进程退出 Linux 下进程的退出分为正常退出和异常退出两种 1 正常退出 a 在main 函数中执行return b 调用exit 函数 c 调用 exit 函数 2 异常退出 a 调用about函数 b 进程收到某个信号 而该信号使程序
  • 【试题】排列组合

    在写一个远程的代码 如果本地有M个显示器 远程有N个显示器 M lt N 依据分辨率 显示器刷新频率等要求 需要对远程的N个显示器进行最佳分辨率修改 之后 需要从N个远程显示器中选择M个 跟本地显示器进行一对一的匹配 即从 A N M N
  • 查找数组中第二大的数

    快速找出一个数组中的最大数 第二大数 思路 如果当 前元素大于最大数 max 则让第二大数等于原来的最大数 max 再把当前元素的值赋给 max 如果当前的元素大于等于第二大数secondMax的值而小于最大数max的值 则要把当前元素的值
  • 插入排序超详解释,一看就懂

    目录 一 插入排序的相关概念 1 基本思想 2 基本操作 有序插入 二 插入排序的种类 三 直接插入排序 1 直接插入排序的过程 顺序查找法查找插入位置 2 使用 哨兵 直接插入排序 四 直接插入排序算法描述 五 折半插入排序 1 查找插入
  • Leetcode2661. 找出叠涂元素

    Every day a Leetcode 题目来源 2661 找出叠涂元素 解法1 哈希 题目很绕 理解题意后就很简单 由于矩阵 mat 中每一个元素都不同 并且都在数组 arr 中 所以首先我们用一个哈希表 hash 来存储 mat 中每
  • 【数据结构入门精讲 | 第二篇】一文讲清算法复杂度

    上篇文章中我们引入了算法 数据结构 数据类型等概念 而要想衡量一个算法与数据结构是否为优质的 就需要一个衡量标准 这个衡量标准也是在我们实现一个好的算法时要遵循的原则 目录 基本概念 渐进性态 渐进性态数学表征 算法复杂度的运算 顺序搜索算
  • 按照层次遍历结果打印完全二叉树

    按照层次遍历结果打印完全二叉树 按照推论结果 l 层首个节点位置 2 h l 1 l 层节点间距 2 h l 1 1 编码实现 public static
  • 排序:计数排序

    一 概念 计数排序是非比较排序 是对哈希直接定址法的变形应用 二 思想 利用数组统计相同数据出现的次数 例如整型数据m出现n次 就在数组m位置记录数据为n 最后从头遍历数组打印数据即可 通俗来讲就是 数组下标即为数据 下标所指位置的值即为数
  • 高精度运算合集,加减乘除,快速幂,详细代码,OJ链接

    文章目录 零 前言 一 加法 高精度加法步骤 P1601 A B 二 减法 高精度减法步骤

随机推荐

  • Linux 中的$* $@特殊变量介绍

    1 代表输入的所有参数 但是看做一个整体 代表输入的所有参数 但是每个区分对待 PS 当 不被双引号括起来的时候 都以 1 2 n的形式输出所有参数 也就是说 当你使用这两个特殊变量的时候 如果不适用双引号括起来 这两个特殊变量的功能就没有
  • Linux alien命令

    一 简介 alien是一个用于在各种不同的Linux包格式相互转换的工具 其最常见的用法是将 rpm转换成 deb 或者反过来 二 安装 http toutiao com a6188997768449360129 三 实例 http www
  • sqlmap参数详解

    命令及详解 h 帮助 version 版本号 d 连接数据库 mysql root root 192 168 3 20 3306 db 数据库种类 账号 密码 地址 端口 库 current db 当前数据库 dbs 列出所有数据库 等于s
  • 软件测试是干什么的 1分钟带你快速了解清楚软测的工作性质

    近几年 国内软件测试行业迅猛发展 不少行外人都能经常听到某某软件测试岗位在高薪招聘消息 等 所以很多不了解情况的人就想要问了 软件测试到底是干什么的 什么样的人才能够当软件测试员 关于大家关心这两个问题 小编特做了如下回答 软件测试是干什么
  • Selenium RemoteWebDriver使用—让你的代码与测试分离(远程测试)

    目录 一 写在前面 二 RemoteWebDriver基本使用 2 1 配置环境 2 2 配置环境命令 2 3 代码示例 三 扩展使用 3 1 浏览器版本和平台参数 3 2 浏览器启动相关参数 一 写在前面 在学习Selenium基础的时候
  • 【实践篇】领域驱动设计:DDD工程参考架构

    背景 为什么要制定参考工程架构 不同团队落地DDD所采取的应用架构风格可能不同 并没有统一的 标准的DDD工程架构 有些团队可能遵循经典的DDD四层架构 或改进的DDD四层架构 有些团队可能综合考虑分层架构 整洁架构 六边形架构等多种架构风
  • Python 常用基础模块(四):sys模块

    目录 一 sys模块介绍 1 1 什么是 Python 解释器 说明 1 2 sys 模块的作用 二 常用方法及属性介绍 2 1 modules属性 将模块名称映射到已加载模块的字典 2 2 getdefaultencoding 方法 获取
  • YOGA 14s开机黑屏——试试提高亮度

    联想yoga 14s 开始动画是有的 但开机动画后就黑屏了 折腾了半天 按下亮度增大键后屏幕亮了 好像联想笔记本比较支持亮度最低即为0
  • 一周简报(项目尾声)

    XX海油项目已经进入尾声 大部分的工作都已经完成 目前我们所做的就是完善系统中的Bug 以及面对客户提出的某些部分的需求变更 由于形式所迫 我们的战斗由 城市 转入 农村 由 地上 转入 地下 由 阵地战 转为 游击战 我们当前的任务是以客
  • 通过源码包*.src.rpm定制开发rpm

    为什么80 的码农都做不了架构师 gt gt gt 1 基本流程 1 下载 安装相应的src rpm包 wget xxx src rpm rpm ivh xxx src rpm 这里的 安装 是指把xxx src rpm中的tar gz p
  • 活动报名

    活动议程 日期 5月5日 周五 时间 主题 14 30 14 35 开场简介 袁洋 清华大学交叉信息学院助理教授 青源会会员 14 35 15 20 环境不变最小二乘回归 方聪 北京大学智能学院助理教授 青源会会员 15 20 15 50
  • 计算机网络分组交换特点,分组交换技术在计算机网络技术中的作用及特点是什么?...

    分组交换是以分组为单位进行传输和交换的 它是一种存储 转发交换方式 即将到达交换机的分组先送到存储器暂时存储和处理 等到相应的输出电路有空闲时再送出 采用存储转发的分组交换技术 实质上是在计算机网络的通信过程中动态分配传输线路或信道带宽的一
  • Android中实现全屏、无标题栏的两种办法(另附Android系统自带样式的解释)

    在进行UI设计时 我们经常需要将屏幕设置成无标题栏或者全屏 要实现起来也非常简单 主要有两种方法 配置xml文件和编写代码设置 1 在xml文件中进行配置 在项目的清单文件AndroidManifest xml中 找到需要全屏或设置成无标题
  • c++ 二进制、八进制、十进制、十六进制相互转换

    itoa 和strtol 可以实现二进制 八进制 十进制 十六进制之间的相互转换 包含在 inculde lt cstdlib gt 1 十进制转换为其他进制 使用itoa int dec char str int R 将十进制数dec转换
  • python执行JavaScript代码

    1 简单使用 import execjs execjs eval new Date 返回值为 2018 04 04T12 53 17 759Z execjs eval Date now 返回值为 1522847001080 需要注意的是返回
  • selenium 获取属性值的两种方法

    初衷是因为要通过属性值判断是否按钮是否disabled 获取属性值的两种方法 1 通过js获取 class text dr execute script return arguments 0 getAttribute class TAG a
  • 关于“service iptables save“的“命令只支持LSB动作”的报错解决方法

    1 报错复现 service iptables save 报错如图 2 解决方式 2 1 先停止防火墙 systemctl stop firewalld 2 2 执行 yum install y iptables service 执行完毕后
  • 四路服务器销售排名,专注企业核心业务 新华三四路服务器2019上半年销售额占比持续增长...

    近日 IDC发布的 2019年第二季度中国x86服务器市场跟踪报告 显示 2019年上半年 紫光旗下新华三集团四路服务器在中国市场销售额排名第二 市场份额环比大幅增长 从中国市场销销售额数据来看 2018年下半年 新华三集团四路服务器市场销
  • QT实现多线程,以及子线程调用主线程方法与变量

    实现思路 第一步需要将子线程声明为主线程的友元类 第二步是将主线程类对象的地址通过信号槽传递给子线程中创建的对象 使得子线程能访问主线程的数据的 1 子线程 displayresult h 头文件 伪代码 include tabwindow
  • 算法学习——贪心算法之币种统计

    算法描述 币种统计 单位给每一位员工发工资 精确到元 为了保证不临时换零钱 使得每个员工取款的张数最少 在取工资前统计所有员工所需要的各种票面的张数 约定票种为100 50 20 10 5 2 1元 并验证币种统计是否正确 算法思路 算法描