算法学习——贪心算法之币种统计
2023-02-18 16:39:50 时间
算法描述
币种统计
单位给每一位员工发工资(精确到元),为了保证不临时换零钱,使得每个员工取款的张数最少,在取工资前统计所有员工所需要的各种票面的张数(约定票种为100,50,20,10,5,2,1元),并验证币种统计是否正确
算法思路
-
算法描述其实是省略了要求,用户肯定是要输入员工数以及各位员工的工资
定义:
n位员工,G[n]对应了第n员工的工资
-
a数组存放100元到1元的面值,a[0]=100,a[1]=50...
-
b数组对应每个面值的张数,b[0]对应100元的张数,b[1]对应50元的张数...
-
采用贪心策略,每次取最大面值
算法实现
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("该算法正确!");
}
结果
相关文章
- [PHP] substr占用内存谨慎使用
- [PHP] 使用ftell和fseek函数直接定位文件位置获取部分数据
- [HTML5] Canvas绘制简单形状
- [PHP]socket的连接超时 与 读取/写入超时
- [PHP]引用返回与节省内存
- [PHP]实体类基类和序列化__sleep问题
- [PHP]日志处理error_log()函数和配置使用
- [PHP] 使用反射实现的控制反转
- [PHP] debug_backtrace()可以获取到代码的调用路径追踪
- [Redis] redis数据备份恢复与持久化
- [PHP] 商品类型规格属性后台管理(代码流程备忘)
- [TCP/IP] TCP的传输连接管理
- [PHP] sys_get_temp_dir()和tempnam()函数报错与环境变量的配置问题
- [PHP] ubuntu下使用uuid扩展获取uuid
- [PHP] MIME邮件协议的multipart类型
- [MySQL] mysql的逻辑分层
- [TCP/IP] 传输层-ethereal 抓包分析TCP包
- [TCP/IP] 传输层-TCP和UDP的使用场景
- [TCP/IP] 网络层-简单查看路由表
- [TCP/IP] 网络层-抓包分析IP数据包首部