贪心:P2240 【深基12.例1】部分背包问题

2024-04-13 05:20

本文主要是介绍贪心:P2240 【深基12.例1】部分背包问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 【深基12.例1】部分背包问题
    • 题目描述
    • 输入格式
    • 输出格式
    • 样例 #1
      • 样例输入 #1
      • 样例输出 #1
    • 代码实现

【深基12.例1】部分背包问题

题目描述

阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 N ( N ≤ 100 ) N(N \le 100) N(N100) 堆金币,第 i i i 堆金币的总重量和总价值分别是 m i , v i ( 1 ≤ m i , v i ≤ 100 ) m_i,v_i(1\le m_i,v_i \le 100) mi,vi(1mi,vi100)。阿里巴巴有一个承重量为 T ( T ≤ 1000 ) T(T \le 1000) T(T1000) 的背包,但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割,分割完的金币重量价值比(也就是单位价格)不变。请问阿里巴巴最多可以拿走多少价值的金币?

输入格式

第一行两个整数 N , T N,T N,T

接下来 N N N 行,每行两个整数 m i , v i m_i,v_i mi,vi

输出格式

一个实数表示答案,输出两位小数

样例 #1

样例输入 #1

4 50
10 60
20 100
30 120
15 45

样例输出 #1

240.00

代码实现

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;public class Main{public static void main(String[] args) {// TODO Auto-generated method stubScanner sc = new Scanner(System.in);int N = sc.nextInt();// N堆金币int T = sc.nextInt();// 背包容量Tdouble[][] arr = new double[N][3];// 每堆金币的重量和价值,以及单价double maxValue = 0;// 最大价值for (int i = 0; i < N; i++) {arr[i][0] = sc.nextDouble();// 总重量arr[i][1] = sc.nextDouble();// 总价值arr[i][2] = arr[i][1] / arr[i][0];// 单价}// 根据单价降序排序Arrays.sort(arr, new Comparator<double[]>() {public int compare(double[] o1, double[] o2) {return Double.compare(o2[2], o1[2]); // 按第三列降序排序}});// 从最大单价开始取金币for (int i = 0; i < N; i++) {if (T >= arr[i][0]) {// 当前背包大于当前堆的金币重量maxValue += arr[i][1];// 累加金币价值T -= arr[i][0];// 背包容量减少} else {// 反之小于:将背包装满之后,结束循环maxValue += arr[i][2] * T;T = 0;// 清空背包break;}}System.out.printf("%.2f", maxValue);// 保留两位小数}}

这篇关于贪心:P2240 【深基12.例1】部分背包问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/899225

相关文章

mybatis和mybatis-plus设置值为null不起作用问题及解决

《mybatis和mybatis-plus设置值为null不起作用问题及解决》Mybatis-Plus的FieldStrategy主要用于控制新增、更新和查询时对空值的处理策略,通过配置不同的策略类型... 目录MyBATis-plusFieldStrategy作用FieldStrategy类型每种策略的作

linux下多个硬盘划分到同一挂载点问题

《linux下多个硬盘划分到同一挂载点问题》在Linux系统中,将多个硬盘划分到同一挂载点需要通过逻辑卷管理(LVM)来实现,首先,需要将物理存储设备(如硬盘分区)创建为物理卷,然后,将这些物理卷组成... 目录linux下多个硬盘划分到同一挂载点需要明确的几个概念硬盘插上默认的是非lvm总结Linux下多

Python Jupyter Notebook导包报错问题及解决

《PythonJupyterNotebook导包报错问题及解决》在conda环境中安装包后,JupyterNotebook导入时出现ImportError,可能是由于包版本不对应或版本太高,解决方... 目录问题解决方法重新安装Jupyter NoteBook 更改Kernel总结问题在conda上安装了

pip install jupyterlab失败的原因问题及探索

《pipinstalljupyterlab失败的原因问题及探索》在学习Yolo模型时,尝试安装JupyterLab但遇到错误,错误提示缺少Rust和Cargo编译环境,因为pywinpty包需要它... 目录背景问题解决方案总结背景最近在学习Yolo模型,然后其中要下载jupyter(有点LSVmu像一个

解决jupyterLab打开后出现Config option `template_path`not recognized by `ExporterCollapsibleHeadings`问题

《解决jupyterLab打开后出现Configoption`template_path`notrecognizedby`ExporterCollapsibleHeadings`问题》在Ju... 目录jupyterLab打开后出现“templandroidate_path”相关问题这是 tensorflo

如何解决Pycharm编辑内容时有光标的问题

《如何解决Pycharm编辑内容时有光标的问题》文章介绍了如何在PyCharm中配置VimEmulator插件,包括检查插件是否已安装、下载插件以及安装IdeaVim插件的步骤... 目录Pycharm编辑内容时有光标1.如果Vim Emulator前面有对勾2.www.chinasem.cn如果tools工

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

Java多线程父线程向子线程传值问题及解决

《Java多线程父线程向子线程传值问题及解决》文章总结了5种解决父子之间数据传递困扰的解决方案,包括ThreadLocal+TaskDecorator、UserUtils、CustomTaskDeco... 目录1 背景2 ThreadLocal+TaskDecorator3 RequestContextH

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列,例如 nums = [10, 9, 2