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

备战蓝桥杯 Day11(滚动数组优化+完全背包)

01背包的滚动数组优化

【题目描述】

经典0—1背包问题,有n个物品,编号为i的物品的重量为w[i],价值为c[i],现在要从这些物品中选一些物品装到一个容量为m的背包中,使得背包内物体在总重量不超过m的前提下价值尽量大。

#include<iostream>
using namespace std;const int N = 3500, M = 12800;
int m, n, w[N], v[N], dp[M];
//状态 dp[j] 前i件物品在背包容量不超过j的情况下的最大价值
//状态转移方程 if (j >= w[i]) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
int main() {cin >> n >> m;for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];//01背包的滚动数组优化for (int i = 1; i <= n; i++){for (int j = m; j >= w[i]; j--) //01背包滚动数组优化的时候,注意j要逆推{dp[j] = max(dp[j],dp[j-w[i]]+v[i]);}}cout << dp[m] << endl;return 0;
}

 完全背包

特点:n种物品,每件物品有无限件(但其实是有限 m/w[i]件

1268:【例9.12】完全背包问题

【题目描述】

设有n�种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为M�,今从n�种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于M�,而价值的和为最大。

#include<iostream>
using namespace std;const int N = 30, M = 200;
int m, n, w[N], v[N], dp[M];
//状态 dp[j] 前i种物品在背包容量不超过j的情况下的最大价值
//状态转移方程
/*
dp[j]=max{dp[j-0*w[i]]+0*v[i],dp[j-1*w[i]]+1*v[i],dp[j-2*w[i]]+2*v[i],dp[j-3*w[i]]+3*v[i],...dp[j-m/w[i]*w[i]]+m/w[i]*v[i]}
*/
int main() {cin >> m >> n;for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];//完全背包朴素版本for (int i = 1; i <= n; i++)for (int j = m; j >= 1; j--)for (int k = 1; k <= m / w[i]; k++)if(j>=k*w[i]) dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]);cout <<"max=" << dp[m] << endl;return 0;
}

多重背包

1269:【例9.13】庆功会

【题目描述】

为了庆贺班级在校运动会上取得全校第一名成绩,班主任决定开一场庆功会,为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品,可以补充他们的精力和体力。

多重背包

特点:n种物品,每件物品有指定数量s[i](真实数量上限:min(m/w[i],s[i])

状态 dp[j] 前i种物品在背包容量不超过j的情况下的最大价值

int main() { cin  >> n >> m;for (int i = 1; i <= n; i++) cin >> w[i] >> v[i]>>s[i];//多重背包朴素版本for (int i = 1; i <= n; i++)for (int j = m; j >= 1; j--)for (int k = 1; k <= min(m / w[i], s[i]); k++)//针对第i种物品,得到选k件的最优解if (j >= k * w[i]) dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]);cout << dp[m] << endl;return 0;
}

相关文章:

备战蓝桥杯 Day11(滚动数组优化+完全背包)

01背包的滚动数组优化 【题目描述】 经典0—1背包问题,有n个物品&#xff0c;编号为i的物品的重量为w[i]&#xff0c;价值为c[i]&#xff0c;现在要从这些物品中选一些物品装到一个容量为m的背包中&#xff0c;使得背包内物体在总重量不超过m的前提下价值尽量大。 #include&…...

Java SE 入门到精通—4.抽象类与接口【Java】

抽象类 同接口一样&#xff0c;用来约束子类&#xff0c;限制子类必须拥有某些方法&#xff0c;比普通类多了个抽象方法&#xff0c;用抽象方法该类必为抽象类 概念 没有具体的对象&#xff0c;具体的方法的一个类 abstract关键字声明为抽象类/方法 一个类中有抽象方法则该…...

Python 开发转 Java 简易路线 - 更新中

有了 Python 开发基础&#xff0c;Java 的内容都可以快速过一遍&#xff0c;复杂地方跟着写一遍。 一、基础 1、Java 基础&#xff1a;尚硅谷 - Java基础 全部快速过一遍&#xff0c; 2、数据库&#xff1a;略。 着重 mysql 高级部分&#xff08;针对面试&#xff09;&…...

Python编程语言学习

1.Python 特点 Python是一种简单、易读、易学和高效的编程语言&#xff0c;具有以下特点&#xff1a; 简单易学&#xff1a;Python采用清晰简洁的语法&#xff0c;注重代码的可读性和可维护性&#xff0c;使得初学者能够快速上手并编写出清晰的代码。 面向对象&#xff1a;Py…...

Cartographer框架简述

catographer框架分为前端和后端 前端包括雷达数据处理&#xff1b;位姿预测&#xff1b;扫描匹配和栅格地图更新。 后端包括后端&#xff1a;线程池任务与调度&#xff1b;向位姿图添加节点&#xff0c;计算节点的子图内约束和子图间约束&#xff08;回环检测&#xff09;&…...

适用于 Linux、Windows 和 macOS 的免费 ONLYOFFICE 桌面应用程序

前言&#xff1a; 最近也是发现了一款特别好用的免费ONLYOFFICE 桌面应用程序忍不住分享给大家&#xff0c;这款编辑器能够打开、阅读和编辑多种文件类型&#xff0c;包括.docx文档、.pptx幻灯片和.xlsx表格等开放XML格式的Office文档。此外&#xff0c;ONLYOFFICE桌面编辑器还…...

C++面向对象程序设计-北京大学-郭炜【课程笔记(四)】

C面向对象程序设计-北京大学-郭炜【课程笔记&#xff08;四&#xff09;】 1、this指针1.1、this指针的作用1.2、this指针和静态成员函数 2、静态成员变量和静态成员函数2.1、基本概念2.2、基本概念总结2.3、如何访问静态成员2.4、静态成员变量的使用场景&#xff08;重要&…...

前端构建效率优化之路

项目背景 我们的系统&#xff08;一个 ToB 的 Web 单页应用&#xff09;前端单页应用经过多年的迭代&#xff0c;目前已经累积有大几十万行的业务代码&#xff0c;30 路由模块&#xff0c;整体的代码量和复杂度还是比较高的。 项目整体是基于 Vue TypeScirpt&#xff0c;而构…...

react实现拖拽的插件

插件一&#xff1a;dnd-kit 插件官网链接https://docs.dndkit.com/introduction/installation 插件二&#xff1a;react-beautiful-dnd https://github.com/atlassian/react-beautiful-dnd/tree/master 两个插件的区别&#xff1a; 插件一可以做到从区域A拖住到区域B 插件二…...

解决Uncaught SyntaxError: Cannot use import statement outside a module(at XXX)报错

报错原因&#xff1a;这个错误通常是因为你正在尝试在一个不支持 ES6 模块语法的环境中使用 import 语句。这可能是因为你的代码是在一个只支持 CommonJS 或 AMD 模块系统的环境中运行的&#xff0c;或者你的代码运行的环境没有正确配置以支持 ES6 模块。如果是在浏览器环境&am…...

PHP如何利用post与get方式传值接收数据

目录 一、POST传值1. 使用curl库发送 POST 请求&#xff1a;2. 使用file_get_contents()函数发送 POST 请求&#xff1a;3. 使用stream_socket_client()函数发送 POST 请求&#xff1a;4. 利用from表单提交数据&#xff1a; 二、GET传值1. 使用http_build_query()函数构建 URL …...

在Mac上搭建MongoDB环境

最近工作中需要装MongoDB环境&#xff0c;搭建过程中遇到了一些问题&#xff0c;在这里记录一下安装MongoDB环境的方法以及问题的解决方法。有两种安装MongoDB的方法&#xff1a;brew安装和手动安装。 目录 使用Homebrew安装MongoDB 手动安装MongoDB&#xff08;不使用Homebr…...

第三十九天| 62.不同路径、63. 不同路径 II

Leetcode 62.不同路径 题目链接&#xff1a;62 不同路径 题干&#xff1a;一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角&#xff08;在下图中标记为 “…...

提高代码质量的 10 条编码原则

提高代码质量的 10 条编码原则 本文转自 公众号 ByteByteGo&#xff0c;如有侵权&#xff0c;请联系&#xff0c;立即删除 今天来聊聊提高代码质量的 10 条编码原则。 软件开发需要良好的系统设计和编码标准。我们在下图中列出了 10 条良好的编码原则。 01 遵循代码规范 我们…...

SHERlocked93 的 2017 年终总结

回家的路上有点无聊&#xff0c;简短回顾一下2017年的得失收获 开始两个月3月到5月用C#完结了一个烂尾的wpf小项目&#xff0c;对自己前半年的.net生涯也算是一个句号&#xff08;虽然不知道最后有没有采用&#xff09;&#xff0c;后面由于项目组转变技术栈&#xff0c;选择了…...

【FreeRTOS基础入门】任务通知

文章目录 前言一、任务通知介绍1.1 任务通知怎么通信1.2 任务通知与其他通信方式的区别1.3 优势及限制任务通知的优势任务通知的限制 1.4 内部原理 二、任务通知的使用2.1 发出与接收通知简化版2.1 发出与接收通知专业版 总结 前言 FreeRTOS 提供了丰富而灵活的任务通知机制&a…...

python opencv比较图片相似度

目录 一:均值哈希算法 二:三直方图算法 三:单通道直方图 一:均值哈希算法 均值哈希算法是一种快速比较图像相似度的方法。它首先将图像转化为灰度图像,然后计算图像的均值,接着将每个像素的...

校园兼职|大学生校园兼职小程序|基于微信小程序的大学生校园兼职系统设计与实现(源码+数据库+文档)

大学生校园兼职小程序目录 目录 基于微信小程序的大学生校园兼职系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、用户​微信端功能模块​ 2、管理员服务端功能模块 &#xff08;1&#xff09; 兼职管理 &#xff08;2&#xff09;论坛管理 &#xff08;3&…...

linux系统离线安装docker服务教程

1、下载、上传docker-20.10.0.tgz压缩包至服务器&#xff0c;其中&#xff0c;docker下载地址https://download.docker.com/linux/static/stable/x86_64/ 2、新建安装docker脚本docker-install.sh #!/usr/bin/env bash tar -xvf docker-20.10.0.tgzcp docker/* /usr/bin/cat …...

【青龙】快速搭建青龙面板,部署属于你自己的应用!

青龙面板是一个支持 Python3、JavaScript、Shell、Typescript 的定时任务管理平台。 废话不多说&#xff0c;直接开始。 这里使用一台 雨云 的云服务器作为演示。雨云注册地址&#xff1a;https://www.rainyun.com/ 优惠码&#xff1a;lz932 使用优惠码注册后绑定微信可获得8折…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

篇章二 论坛系统——系统设计

目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...

Python学习(8) ----- Python的类与对象

Python 中的类&#xff08;Class&#xff09;与对象&#xff08;Object&#xff09;是面向对象编程&#xff08;OOP&#xff09;的核心。我们可以通过“类是模板&#xff0c;对象是实例”来理解它们的关系。 &#x1f9f1; 一句话理解&#xff1a; 类就像“图纸”&#xff0c;对…...

高效的后台管理系统——可进行二次开发

随着互联网技术的迅猛发展&#xff0c;企业的数字化管理变得愈加重要。后台管理系统作为数据存储与业务管理的核心&#xff0c;成为了现代企业不可或缺的一部分。今天我们要介绍的是一款名为 若依后台管理框架 的系统&#xff0c;它不仅支持跨平台应用&#xff0c;还能提供丰富…...

RabbitMQ 各类交换机

为什么要用交换机&#xff1f; 交换机用来路由消息。如果直发队列&#xff0c;这个消息就被处理消失了&#xff0c;那别的队列也需要这个消息怎么办&#xff1f;那就要用到交换机 交换机类型 1&#xff0c;fanout&#xff1a;广播 特点 广播所有消息​​&#xff1a;将消息…...