蓝桥杯 ADV168 算法提高 快乐司机(贪心 快排)(java)
发布日期:2021-06-28 15:58:09
浏览次数:2
分类:技术文章
本文共 2181 字,大约阅读时间需要 7 分钟。
算法提高 快乐司机
时间限制:1.0s 内存限制:256.0MB
问题描述
"嘟嘟嘟嘟嘟嘟
喇叭响
我是汽车小司机
我是小司机
我为祖国运输忙
运输忙"
这是儿歌“快乐的小司机”。话说现在当司机光有红心不行,还要多拉快跑。多拉不是超载,是要让所载货物价值最大,特别是在当前油价日新月异的时候。司机所拉货物为散货,如大米、面粉、沙石、泥土......
现在知道了汽车核载重量为w,可供选择的物品的数量n。每个物品的重量为gi,价值为pi。求汽车可装载的最大价值。(n<10000,w<10000,0<gi<=100,0<=pi<=100)
喇叭响
我是汽车小司机
我是小司机
我为祖国运输忙
运输忙"
这是儿歌“快乐的小司机”。话说现在当司机光有红心不行,还要多拉快跑。多拉不是超载,是要让所载货物价值最大,特别是在当前油价日新月异的时候。司机所拉货物为散货,如大米、面粉、沙石、泥土......
现在知道了汽车核载重量为w,可供选择的物品的数量n。每个物品的重量为gi,价值为pi。求汽车可装载的最大价值。(n<10000,w<10000,0<gi<=100,0<=pi<=100)
输入格式
输入第一行为由空格分开的两个整数n w
第二行到第n+1行,每行有两个整数,由空格分开,分别表示gi和pi
第二行到第n+1行,每行有两个整数,由空格分开,分别表示gi和pi
输出格式
最大价值(保留一位小数)
样例输入
5 36
99 87
68 36
79 43
75 94
7 35
99 87
68 36
79 43
75 94
7 35
样例输出
71.3
解释:
先装第5号物品,得价值35,占用重量7
再装第4号物品,得价值36.346,占用重量29
最后保留一位小数,得71.3
解释:
先装第5号物品,得价值35,占用重量7
再装第4号物品,得价值36.346,占用重量29
最后保留一位小数,得71.3
这里用到了贪心算法,
先计算每一个物品的单位价值(pi价值/gi每个物品的重量),每一次把单位价值最高的物品装进车子里。当车的重量小于要装的重量,则把(剩下要装的物品的重量 乘以 单位物品的价值)都装进车里;当车的重量大于等于要装的重量,则把那个全部物品装进车里。。
第一次做的代码和第二次做的代码,区别在于:当w大于所有货物加起来的重量时,程序就会进入死循环,因为w会一直大于0,而那个flag是控制当所有的货物遍历完了,都没找到一个最大价值时,退出while循环。
(感谢一起参加蓝桥杯的同学)
第一次做的代码如下:(90分)
import java.util.Scanner;public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner = new Scanner(System.in); int n = scanner.nextInt();//数量 double w = scanner.nextInt();//重量 //第3列为:每一个物品的单位重量的价值 //第4列为:判断物品是否已经装进车里了,如果装进车里了则为1,还没有装进车的则为0 double[][] arr = new double[n][4]; for(int i=0;i第二次做的代码如下:(100分)0){//当车载重大于0的时候,还可以载物品 double max=0; int index = 0; for(int i=0;i max&&arr[i][3]==0){ max=arr[i][2]; index=i; } if(i==n-1){//每次检测最后一个,把最大值的下标赋1 arr[index][3]=1; } } if(w =arr[index][0]){//车的重量大于等于要载的重量 result+=arr[index][1]; w-=arr[index][0]; } } System.out.printf("%.1f",result); }}
import java.util.Scanner;public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner = new Scanner(System.in); int n = scanner.nextInt();//数量 double w = scanner.nextDouble();//重量 double[][] arr = new double[n][4]; //第3列为:每一个物品的单位重量的价值 //第4列为:判断物品是否已经装进车里了,如果装进车里了则为1,还没有装进车为0 for(int i=0;i0){//当车载重大于0的时候,还可以载物品 double max=0; int index=0; boolean flag=true; for(int i=0;i max&&arr[i][3]==0){ max=arr[i][2]; index=i; flag=false; } } arr[index][3]=1; if(flag){ break; } if(w =arr[index][0]) result+=arr[index][1]; w-=arr[index][0]; } } System.out.printf("%.1f",result); }}
转载地址:https://blog.csdn.net/xiaodingqq/article/details/78829987 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年04月17日 10时28分46秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
【免费】少儿编程社区,Scratch中文社区,少儿编程学习交流平台上线~~~
2019-04-29
JavaMail关于使用qq企业邮箱发邮件踩过的坑
2019-04-29
log4j2异步发送error日志邮件配置
2019-04-29
redis setnx解决定时任务多节点部署并发问题(分布式锁)
2019-04-29
spring boot使用redis解决session双机问题
2019-04-29
Java Web会话机制,Cookie和Session详解
2019-04-29
基于timestamp和nonce的防止重放攻击方案
2019-04-29
Linux常用基础命令198个
2019-04-29
Linux运维工程师初级面试题
2019-04-29
GA入门
2019-04-29
kettle问题合集
2019-04-29
spark学习笔记
2019-04-29
Tableau学习笔记
2019-04-29
Kettle学习笔记
2019-04-29
airflow问题合集
2019-04-29
sql
2019-04-29
BI分析
2019-04-29
springboot+mybatis+sharding-jdbc整合分库分表实战
2019-04-29
linux查看文件命令介绍
2019-04-29