当前位置: 首页 > news >正文

【3】贪心算法-最优装载问题-加勒比海盗

算法背景
在北美洲东南部,有一片神秘的海域,那里碧海蓝天、阳光
明媚,这正是传说中海盗最活跃的加勒比海(Caribbean Sea)。
有一天,海盗们截获了一艘装满各种各样古董的货船,每一
件古董都价值连城,一旦打碎就失去了它的价值。虽然海盗船足
够大,但载重量为C,每件古董的重量为wi,海盗们该如何把尽
可能多数量的宝贝装上海盗船呢?
在这里插入图片描述

问题分析
贪心策略
本题要求物品不可分割,要求装载的物品的数量尽可能多,而船的载重量
是固定的,那么优先把重量小的物品放进去,在载重量固定的情况下,装的物
品最多。
贪心选择策略:重量最小者先装
从局部最优达到全局最优,从而产生最优装载问题的最优解。
算法设计
算法设计:
(1)当载重量为定值c时,wi越小时,可装载的古董数量n越大。只要依次选
择最小重量古董,直到不能再装为止。
(2)把n个古董的重量从小到大(非递减)排序,然后根据贪心策略尽可能多
地选出前i个古董,直到不能继续装为止,此时达到最优。
完美图解
在这里插入图片描述
表2-1 古董重量清单
在这里插入图片描述
(1)因为贪心策略是每次选择重量最小的古董装入海盗船,因此可以按照古董重
量非递减排序,排序后如表2-2所示。

表2-2 按重量排序后古董清单
在这里插入图片描述
(2)按照贪心策略,每次选择重量最小的古董放入(tmp 代表古董的重量,ans
代表已装裁的古董个数)。
在这里插入图片描述
算法的伪代码
在这里插入图片描述
实战演练
在这里插入图片描述
在这里插入图片描述

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e6 + 10;
int q[maxn];//宝物重量的数组 
int n,max1;//n-宝物的数量;max1-串只所能载的最大重量 
int main(){cin>>n>>max1;int sum1 = 0;int count = 0;//船能装载货物的数量 for(int i = 0;i <= n - 1;i ++){cin>>q[i];}sort(q,q+n);for(int i = 0;i <= n - 1;i ++){sum1 += q[i];count ++;if(sum1 > max1){sum1 -= q[i];break;}}cout<<sum1<<endl;cout<<count - 1<<endl;return 0;}

相关文章:

【3】贪心算法-最优装载问题-加勒比海盗

算法背景 在北美洲东南部&#xff0c;有一片神秘的海域&#xff0c;那里碧海蓝天、阳光 明媚&#xff0c;这正是传说中海盗最活跃的加勒比海&#xff08;Caribbean Sea&#xff09;。 有一天&#xff0c;海盗们截获了一艘装满各种各样古董的货船&#xff0c;每一 件古董都价值连…...

JavaScript 的 for 循环应该如何学习?

JS for 循环语法 JS for 循环适合在已知循环次数时使用&#xff0c;语法格式如下&#xff1a; for(initialization; condition; increment) {// 要执行的代码 }for 循环中包含三个可选的表达式 initialization、condition 和 increment&#xff0c;其中&#xff1a; initial…...

C++核心编程--对象篇

4.2、对象 4.2.1、对象的初始化和清理 用于对对象进行初始化设置&#xff0c;以及对象销毁前的清理数据的设置。 构造函数和析构函数 防止对象初始化和清理也是非常重要的安全问题 一个对象或变量没有初始化状态&#xff0c;对其使用后果是未知的同样使用完一个对象或变量&…...

安装php扩展XLSXWriter,解决php导入excel表格时获取日期变成浮点数的方法

安装php扩展XLSXWriter 1、下载安装包 PECL :: Package :: xlswriter #例如选择下载1.3.6版本 2、解压下载包 tar -zxvf xlswriter-1.3.6.tgz 3、进入文件夹,编译 cd xlswriter-1.3.6 phpize ./configure --with-php-config=/usr/local/php7.1/bin/php-config make&am…...

Vue+element开发Simple Admin后端管理系统页面

最近看到各种admin&#xff0c;头大&#xff0c;内容太多&#xff0c;根本不知道怎么改。所以制作了这个项目&#xff0c;只包含框架、和开发中最常用的表格和表单&#xff0c;不用自己从头搭建架构&#xff0c;同时也容易上手二次开发。可以轻松从其他开源项目整合到本项目。项…...

源码编译安装pkg-config

安装环境&#xff1a;银河麒麟 1 到这个网址下载pkg-config源码&#xff1a; Index of /releases (pkg-config.freedesktop.org) 2 解压 3 进入解压后的目录。输入 ./configure 但是报错。 4 根据报错信息&#xff0c;将configure改为&#xff1a; ./configure --with-i…...

游览器找不到服务器上PHP文件的一种原因

最近在练习搭建网站&#xff0c;遇到游览器找不到服务器上的php文件的问题。后来查找发现&#xff0c;apache文档根目录跟apache虚拟主机文档根目录不同&#xff0c;服务器开启了虚拟主机功能。这导致游览器找不到php文件。使用的环境LAMP 里操作系统和软件版本如下&#xff1a…...

C++之std::function的介绍

C之std::function的介绍 std::function和函数指针的区别介绍std::function 的常见用法包括用法举例 std::function和函数指针的区别介绍 std::function 和函数指针在 C 中都可以用来存储和调用函数&#xff0c;但它们的使用方式和功能有所不同。 函数指针是一种指向函数的指针…...

卷积神经网络学习(一)

CNN应用对象是图像&#xff0c;CNN可被应用于的任务&#xff1a; 1、分类&#xff08;classification&#xff09;&#xff1a;对图像按其中的物体进行分类&#xff0c;如图像中有人与猫&#xff0c;则图像可分为两类。 2、目标检测&#xff08;object detection&#xff09;&a…...

使用KEIL自带的仿真器仿真遇到问题解决

*** error 65: access violation at 0x40021000 : no read permission 修改debug选项设置为下方内容。...

4700 万美元损失,Xn00d 合约漏洞攻击事件分析

4700 万美元损失&#xff0c;Xn00d 合约漏洞攻击事件分析 基础知识 ERC777 ERC777 是 ERC20 标准的高级代币标准&#xff0c;要提供了一些新的功能&#xff1a;运营商及钩子。 运营商功能。通过此功能能够允许第三方账户代表某一合约或者地址 进行代币的发送交易钩子功能。…...

第5讲:v-if与v-show的使用方法及区别

v-if条件判断 v-if是条件渲染指令&#xff0c;它根据表达式的真假来删除和插入元素&#xff0c;它的基本语法如下&#xff1a; v-if “expression” expression是一个返回bool值的表达式&#xff0c;表达式可以是一个bool属性&#xff0c;也可以是一个返回bool的运算式 &#…...

C理解(一):内存与位操作

本文主要探讨C语言的内存和为操作操作相关知识。 冯诺依曼结构和哈佛结构 冯诺依曼结构&#xff1a;数据和代码放在一起,便于读取和修改,安全性低 哈佛结构是&#xff1a;数据和代码分开存放,安全性高,读取和修麻烦 内存 内存是用来存储全局变量、局…...

ESP8266使用记录(四)

放上最终效果 ESP8266&Unity游戏 整合放进了坏玩具车遥控器里 最终只使用了mpu6050的yaw数据&#xff0c;因为roll值漂移…… 使用了https://github.com/ElectronicCats/mpu6050 整个流程 ESP8266取MPU6050数据&#xff0c;处理后通过udp发送给Unity显示出来 MPU6050_Z…...

云原生Kubernetes:K8S安全机制

目录 一、理论 1.K8S安全机制 2.Authentication认证 3.Authorization授权 4.Admission Control准入控制 5.User访问案例 6.ServiceAccount访问案例 二、实验 1.Admission Control准入控制 2.User访问案例 3.ServiceAccount访问案例 三、问题 1.生成资源报错 2.镜…...

【数据结构】归并排序、基数排序算法的学习知识点总结

目录 1、归并排序 1.1 算法思想 1.2 代码实现 1.3 例题分析 2、基数排序 2.1 算法思想 2.2 代码实现 2.3 例题分析 1、归并排序 1.1 算法思想 归并排序是一种采用分治思想的经典排序算法&#xff0c;通过将待排序数组分成若干个子序列&#xff0c;将每个子序列排序&#xff…...

【C++】C++模板进阶 —— 非类型模板参数、模板的特化以及模板的分离编译

​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;C学习 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 上一篇博客&#xff1a;【C】C多…...

HTML的相关知识

1.什么是HTML&#xff1f;基本语法 HTML: Hyper Text Markup Language &#xff08;超文本标记语言&#xff09; 超文本&#xff1f;超级文本&#xff0c;例如流媒体&#xff0c;声音、视频、图片等。 标记语言&#xff1f;这种语言是由大量的标签组成。HTML标签参考手…...

基于微信小程的流浪动物领养小程序设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言系统主要功能&#xff1a;具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序&#xff08;小蔡coding&#xff09;有保障的售后福利 代码参考源码获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计…...

Java后端接口编写流程

&#x1f497;wei_shuo的个人主页 &#x1f4ab;wei_shuo的学习社区 &#x1f310;Hello World &#xff01; Java后端接口编写流程 Java后端接口编写流程&#xff0c;更具业务逻辑编写Java后端接口&#xff0c;提供给前端访问 实现逻辑流程 POJO&#xff1a;实体类编写 Data B…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

Bean 作用域有哪些?如何答出技术深度?

导语&#xff1a; Spring 面试绕不开 Bean 的作用域问题&#xff0c;这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开&#xff0c;结合典型面试题及实战场景&#xff0c;帮你厘清重点&#xff0c;打破模板式回答&#xff0c…...