当前位置: 首页 > 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…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

FFmpeg 低延迟同屏方案

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

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...