精选文章 部分背包问题

部分背包问题

作者:night_dust 时间: 2021-07-04 09:05:46
night_dust 2021-07-04 09:05:46
【摘要】
                    
                        
                    
                    HDU-1009-FatMouse’ Trade 
肥鼠准备了 M 磅的猫粮,准备和看管仓库的猫交易,仓库里装有他最喜爱的食物 Java 豆。  仓库有 N 个房间。第 i 间房包含了 J[i] 磅的 Java 豆,需...

HDU-1009-FatMouse’ Trade

肥鼠准备了 M 磅的猫粮,准备和看管仓库的猫交易,仓库里装有他最喜爱的食物 Java 豆。
仓库有 N 个房间。第 i 间房包含了 J[i] 磅的 Java 豆,需要 F[i] 磅的猫粮。肥鼠不必为了房间中的所有 Java 豆而交易,相反,他可以支付 F[i] * a% 磅的猫粮去交换得到 J[i] * a% 磅的 Java 豆。这里,a 表示一个实数。
现在他将这项任务分配给了你:请告诉他,能够获得的 Java 豆的最大值是多少。

输入
输入包含多组测试数据,对于每组测试数据,以包含了两个非负整数 M 和 N 的一行开始。接下来的 N 行,每行相应包含了两个非负整数 J[i] 和 F[i]。最后一组测试数据是两个 -1。所有的整数均不超过 1000。
输出
对于每组测试数据,在单独的一行中打印一个实数,精确到小数点后 3 位数,表示肥鼠能够取得的 Java 豆的最大值。

示例输入
5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1

示例输出
13.333
31.500

分析:就是一个部分背包的模板体,用一下结构体就行了,也是个贪心,排下序然后从最大开始算。

#include
#include
using namespace std;
struct stu{ double xjb;  //这个是每个房间的性价比 double j,f;  //分别是需要的猫粮和豆子
}de[2000];
bool cmp(stu a,stu b)
{ return a.xjb > b.xjb; //排序
}
int main()
{ int n,i; double m,F,J; while(scanf("%lf%d",&m,&n)!=EOF) { double sum = 0; if(m==-1&&n==-1) break; for(i = 0;i < n; i++){ scanf("%lf%lf",&de[i].j,&de[i].f); de[i].xjb = de[i].j/de[i].f; } sort(de,de+n,cmp); for(i = 0;i < n; i++) { if(m >= de[i].f){  //这个需要比较一下 sum += de[i].j; m -= de[i].f; } else{ sum += de[i].j*(m/de[i].f); break; } } printf("%.3lf\n",sum); } return 0;
}
勿删,copyright占位
您找到想要的结果了吗?
部分背包问题
提交成功!非常感谢您的反馈,我们会继续努力做到更好
分享文章到微博
分享文章到朋友圈

上一篇:Linux fedora28安装powershell

下一篇:部分背包问题

您可能感兴趣

  • 了解Hadoop生态圈的主要部分(初学笔记)

    1、图示生态架构   2、从低往上学 HDFS 直译分布式文件系统,相当于windows机器上的视频、图片、文档等都是存到硬盘上,硬盘再需要做一些格式化。 在Hadoop上需要存储大数据,而且是存储在各个不同的机器上的。所以HDFS也就是一个分布式系统(分布式意思就是一个集群里面有很多台机器)。 HDFS作为一个最基本的文件系统就是存储...

  • Hibernate查询部分字段并封装到指定类中及其可能遇到的问题

    HQL中如果是多对多查询推荐使用@ManyToMany和@JoinTable的方式,可以节省存储空间和简化表结构,但如果是一对多或者多对一时,使用@ManyToOne或@OneToMany反而会产生中间表,表结构本来简单的情况下反而多此一举,只要在多的一方表字段中加入一的一方ID就够用了。不管如何联合查询,往往目的是需要把部分字段封装到特定类,hib...

  • Mybatis部分面试题

    1.JDBC编程有哪些不足之处,MyBatis是如何解决这些问题的? ① 数据库链接创建、释放频繁造成系统资源浪费从而影响系统性能,如果使用数据库链接池可解决此问题。 解决:在SqlMapConfig.xml中配置...

  • PHP 数组部分 -声明的特性

    数组的定义:把若干变量有序的的形式组织起来的一种形式。这些数据元素的集合称为数组 数组 分为一维数组 二维数组 二维以上的就是多维数组。 数组是一个容器,使用的目的是可以批量操作。 数组的分类: 索引数组 和关...

  • 文本分类任务的基础实现(二)——机器学习部分_分类器_代码介绍

    该部分用于文本分类任务的基础实现,主要包括机器学习(ml)和深度学习(dl)两大部分,机器学习部分基于sklearn/lightgbm包实现,深度学习部使用pytorch深度学习框架。 机器学习部分主要包含特征工程和...

  • css实现文字“一行/两行”显示,超出部分省略号显示

    1.文字一行显示: div { width: 150px; overflow: hidden; text-overflow: ellipsis; /* 文字超出部分省略号显示 */ white-space: nowrap; /* 不换行 */ }   2.文字两行显示: div { text-...

  • awk功能及用法,附部分练习题

    awk awk有3个不同版本: awk、nawk和gawk,未作特别说明,一般指gawk,gawk 是 awk 的 GNU 版本,可以使用以下命令来查看awk的版本。 ls -l `which awk` 1、工...

  • 大数据linux系统部分命令解析(2)0912

    1.查看ip ifconfig 解释: ifconfig 常用命令关闭网卡,查看ip。请看帮助! NAME ifconfig - configure a network interface SYNOPSIS ...

CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。
部分背包问题介绍:华为云为您免费提供部分背包问题在博客、论坛、帮助中心等栏目的相关文章,同时还可以通过 站内搜索 查询更多部分背包问题的相关内容。| 移动地址: 部分背包问题 | 写博客