首页 > 其他分享 >【深基12.例1】部分背包问题——仔细检查数据类型!

【深基12.例1】部分背包问题——仔细检查数据类型!

时间:2024-10-30 14:42:14浏览次数:5  
标签:le int 样例 深基 数据类型 金币 12 背包

题目描述

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

输入格式

第一行两个整数 \(N,T\)。

接下来 \(N\) 行,每行两个整数 \(m_i,v_i\)。

输出格式

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

样例 #1

样例输入 #1

4 50
10 60
20 100
30 120
15 45

样例输出 #1

240.00

我的作答

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n,t;
	cin >> n >> t;
	int m[110],v[110];
	double p[110];
	for (int i=0;i<n;i++) {
		cin >> m[i] >> v[i];
		p[i] = (double) v[i] / m[i];
	}
	for (int i=0;i<n-1;i++) {
		for (int j=0;j<n-i-1;j++) {
			if (p[j] < p[j+1]) {
				double temp1 = p[j];
				p[j] = p[j+1];
				p[j+1] = temp1;
				int temp2 = m[j];
				m[j] = m[j+1];
				m[j+1] = temp2;
				int temp3 = v[j];
				v[j] = v[j+1];
				v[j+1] = temp3;
			}
		}
	}
	int sum_m=0;
	double sum_v=0.00;
	for (int i=0;i<n;i++) {
		if ((sum_m+m[i])<t) {
			sum_v += v[i];
			sum_m += m[i];
		} else {
			sum_v += (double)(t-sum_m) * v[i] / m[i];
			sum_m = t;
			break;
		}
	}
	printf("%.2lf",sum_v);
	return 0;
}

反思总结

首先是一个易错点:

	double temp1 = p[j];
	p[j] = p[j+1];
	p[j+1] = temp1;

冒泡排序时,要注意temp1的数据类型正确;我在做本题时就因为这里导致出错。

然后是背包装满的循环问题:

	for (int i=0;i<n;i++) {
		if ((sum_m+m[i])<t) {
			sum_v += v[i];
			sum_m += m[i];
		} else {
			sum_v += (double)(t-sum_m) * v[i] / m[i];
			sum_m = t;
			break;
		}
	}

在装满背包之后,要break跳出循环。(本题不需要)

标签:le,int,样例,深基,数据类型,金币,12,背包
From: https://www.cnblogs.com/xiins/p/18515821

相关文章

  • 关于我、重生到500年前凭借C语言改变世界科技vlog.12——深入理解指针(2)
    文章目录1.数组名与地址1.1arr1.2sizeof(arr)1.3&arr2.指针访问数组3.一维数组传参本质4.指针数组5.二级指针希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力!1.数组名与地址有这么一个数组,数组名为arrintarr[10]={1,2,3,4,5,6,7,8,9}int......
  • 【5】复杂数据类型
    文章目录一、数组与切片(一)数组(二)切片二、map类型(一)map的定义与声明(二)map类型的增删改查(三)Map的长度与切片(四)map类型使用的注意细节三、面向对象与结构体(一)结构体定义(二)结构体变量初始化<结构体是值类型>(三)创建结构体变量的方法(四)结构体使......
  • windows下Mysql8.0.12安装详解
    MySQL的安装过程还是比较繁琐,为了以后安装节约时间,将其详细安装过程总结如下:1>下载对应版本下载地址:https://dev.mysql.com/downloads/mysql/2>将下载的.zip文件解压到需要安装的目录下,在该目录下创建一个名为data的空文件夹和一个my.ini文件3>配置初始化的my.ini文件......
  • SpringBoot人事管理912fw(程序+源码+数据库+调试部署+开发环境)
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表部门,员工,考勤信息,工资发放,员工请假,加班登记,迟到登记,培训信息,报名信息,文档档案,签到信息开题报告内容一、项目背景随着企业规模的扩大,人事管理变得日......
  • C#学习 [类型系统] 命名空间(12)
    作用1.组织类System.Console.WriteLine("HelloWorld!");System是一个命名空间,Console是该命名空间中的一个类。可使用using关键字,这样就不必使用完整的名称。usingSystem;Console.WriteLine("HelloWorld!");控制类和方法名称的范围namespaceSampleNamespace;......
  • 第12课—数据库之视图
    数据库之视图(一)视图的介绍=============================一、什么是视图?视图是一个虚拟表,它是一个虚拟表,它不在数据库中以存储的形式保存(本身不包含数据),是在使用视图的时候动态生成。二、视图的优点?1、提高查询效率数据库中的数据查询非常复杂,可以简化sql语句2、安全有些......
  • C#基础数据类型
    C# 数据类型在C#中,变量分为以下几种类型:值类型(Valuetypes)引用类型(Referencetypes)指针类型(Pointertypes)值类型(Valuetypes)值类型变量可以直接分配给一个值。它们是从类 System.ValueType 中派生的。值类型直接包含数据。比如 int、char、float,它们分别存储数字......
  • 袋鼠云产品功能更新报告12期|让数据资产管理更高效
    本期,我们更新和优化了数据资产平台相关功能,为您提供更高效的产品能力。以下为第12期袋鼠云产品功能更新报告,请继续阅读。一、【元数据】重点更新|01元数据管理优化,支持配置表生命周期之前系统中缺少一个可以基于数据源和数据库维度,批量配置数据表生命周期的入口,导致用户在处理......
  • 9.12
    周四今天没课做一下作业一.单选题(共10题,20分)1. (单选题,2分)‍第三次信息化浪潮的标志是:A. 个人电脑的普及B. 虚拟现实技术的普及C. 云计算、大数据、物联网技术的普及D. 互联网的普及我的答案: C:云计算、大数据、物联网技术的普及;正确答案: C:云计算、大......
  • P11234 [CSP-S 2024] 擂台游戏
    看看了看今年的csps,前三题一眼就秒了,这最后一题想了挺久,还写了快两个小时,要是在正式赛场上估计是要暴毙了,不过好在我已经退役了,希望参赛的选手能有好的发挥题目大意太长了,不写了题解考虑每次加入一个人,然后分析变化的答案经过一些分析,可以发现一些性质1.对于完全没有确定能......