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

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分&#xff1a; 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...