2. 01背包问题
文章目录
- Question
- Ideas
- Code
Question
有 N
件物品和一个容量是 V
的背包。每件物品只能使用一次。
第 i
件物品的体积是 vi
,价值是 wi
。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行两个整数,N,V
,用空格隔开,分别表示物品数量和背包容积。
接下来有 N
行,每行两个整数 vi,wi
,用空格隔开,分别表示第 i
件物品的体积和价值。
输出格式
输出一个整数,表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例:
8
Ideas
Code
#include <iostream>using namespace std;
const int N = 1010;
int f[N];
int w[N], v[N];int main()
{int n, m;scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++) scanf("%d%d", &v[i], &w[i]);// f[0][0~m] = 0, f[0~n][0] = 0for (int i = 1; i <= n; i ++){for (int j = m; j >= v[i]; j --){f[j] = max(f[j], f[j-v[i]]+ w[i]);}}printf("%d", f[m]);return 0;
}
相关文章:
2. 01背包问题
文章目录QuestionIdeasCodeQuestion 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi ,价值是 wi 。 求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。 输出最大价值。 输入…...
【Docker】CAdvisor+InfluxDB+Granfana容器监控
文章目录原生命令 docker stats容器监控3剑客CIGCAdvisorInfluxDBGranfanacompose容器编排,一套带走新建目录新建3件套组合的 docker-compose.yml检查配置,有问题才有输出 docker-compose config -q启动docker-compose文件 docker-compose up -d测试浏览…...
k8s 部署nginx 实现集群统一配置,自动更新nginx.conf配置文件 总结
k8s 部署nginx 实现集群统一配置,自动更新nginx.conf配置文件 总结 大纲 1 nginx镜像选择2 创建configmap保存nginx配置文件3 使用inotify监控配置文件变化4 Dockerfile创建5 调整镜像原地址使用阿里云6 创建deploy部署文件部署nginx7 测试使用nginx配置文件同步&…...
动态内存管理(上)——“C”
各位CSDN的uu们你们好呀,今天,小雅兰的内容是动态内存管理噢,下面,让我们进入动态内存管理的世界吧 为什么存在动态内存分配 动态内存函数的介绍 malloc free calloc realloc 常见的动态内存错误 为什么存在动态内存分配 我们已…...
GPT-4发布,这类人才告急,大厂月薪10W+疯抢
ChatGPT最近彻底火出圈,各行各业都在争相报道,甚至连很多官媒都下场“跟风”。ChatGPT的瓜还没吃完,平地一声雷,GPT-4又重磅发布! 很多小伙伴瑟瑟发抖:“AI会不会跟自己抢饭碗啊?” 关于“如何…...
MySQL数据库实现主主同步
前言 MySQL主主同步实际上是在主从同步的基础上将从数据库也提升成主数据库,让它们可以互相读写数据库,从数据库变成主数据库;主从相互授权连接,读取对方binlog日志并更新到本地数据库的过程,只要对方数据改变,自己就…...
JavaScript传参的6种方式
JavaScript传参的方式1. 传递基本类型参数2. 传递对象类型参数3. 使用解构赋值传递参数4. 使用展开运算符传递参数5. 使用可选参数6. 使用剩余参数JavaScript是一门非常灵活的语言,其参数传递方式也同样灵活。在本篇文章中,会详细介绍JavaScript中的参数…...
蓝桥之统计子矩阵
样例说明 满足条件的子矩阵一共有 19 , 包含: 大小为 11 的有 10 个。 大小为 12 的有 3 个。 大小为13 的有 2 个。 大小为 14 的有 1 个。 大小为 21 的有 3 个。 前缀和二维数组 前缀和暴力搜索 import java.util.*; public class Main{private static int ans0;pub…...
Java的基础面试题
一.java基础1.JDK和JRE有什么区别?JDK是java开发工具包,JRE是java运行时环境(包括Java基础类库,java虚拟机)2.和equals的区别是什么?比较的是两者的地址值,equals比较的是两者的内容是否一样3.两…...
J1939故障码诊断说明
1:1939整体协议说明 这里主要说明1939不同的协议,对应不同的网络分层 注意了,这里只进行文档解析说明,具体查看去搜素协议的关键字进行理解 2:DMx和FMI 说明 想知道每个代号的具体含义,可以去 saeJ1939…...
XCPC第十三站,贪心问题
一.区间选点 我们采取这样的策略来选点:step(1)将区间按照右端点的大小从小到大排序;step(2)从前往后依次枚举每个区间,如果当前区间中已经包含点,直接pass,否则选当前区…...
一文让你吃透 Vue3中的组件间通讯 【一篇通】
文章目录前情回顾前言1. 父组件 > 子组件通讯传递2. 子组件 > 父组件通讯传递3. 爷孙组件,后代组件通讯数据总结前情回顾 在本专栏前一章节中,我为大家带来了 Vue3 新特性变化上手指南 的归纳梳理,主要介绍了 Vue3 的 Proxy 响应式原理…...
EVE遭遇大规模DDOS攻击,玩家和官方都傻眼了
如果你恰好是一名《星战前夜》(EVE)的国际服玩家(虽然这个几率很小),又恰好因为疫情一直待在家里,那你就真是倒霉透顶了。因为从1月底开始,EVE的服务器就一直受到大规模的DDOS攻击,而…...
【数据结构】二叉树及相关习题详解
新年新气象! 祝大家兔年 财源滚滚! 万事胜意! 文章目录前言1. 树的一些基础概念1.1 树的一些基本概念1.2 树的一些重要概念2. 二叉树的一些基本概念2.1 二叉树的结构2.2 两种特殊的二叉树3. 二叉树的性质4. 二叉树的存储5. 二叉树的基本操作5.1 构造一棵二叉树5.2 二叉树的遍历…...
锂电池充电的同时也能放电吗?
大家应该都有这样经历,我们的手机在充电的同时也能边使用,有的同学就会说了,这是因为手机电池在充电的同时也在放电。如果这样想我们可能就把锂电池类比了一个蓄水池,以为它在进水的同时也能出水,其实这个比喻是错误的…...
通信工程考研英语复试专有名词翻译
中文英文频分多址Frequency Division Multiple Access码分多址Code Division Multiple Access时分多址Time Division Multiple Access移动通信mobile communication人工智能artificial intelligence水声通信Middle-Range Uwa Communication正交频分复用Orthogonal frequency di…...
注意力机制(四):多头注意力
专栏:神经网络复现目录 注意力机制 注意力机制(Attention Mechanism)是一种人工智能技术,它可以让神经网络在处理序列数据时,专注于关键信息的部分,同时忽略不重要的部分。在自然语言处理、计算机视觉、语…...
【2023Unity游戏开发教程】零基础带你从小白到超神19——射线检测
文章目录 射线检测从某点发射一条射线从摄像机发射一条射线射线检测 游戏中的红外线,默认肉眼是看不到的,从某个初始点开始,沿着特定的方向发射一条不可见且无限长的射线,通过此射线检测是否有任何模型添加了Collider碰撞器组件。一旦检测到碰撞,停止射线继续发射。 碰撞检…...
内存泄漏和内存溢出的区别
参考答案 内存溢出(out of memory):指程序在申请内存时,没有足够的内存空间供其使用,出现 out of memory。内存泄露(memory leak):指程序在申请内存后,无法释放已申请的内存空间,内存泄露堆积会导致内存被…...
文本三剑客之sed编辑器
文本三剑客:都是按行读取后处理。 grep 过滤行内容。awk 过滤字段。sed 过滤行内容;修改行内容。sed编辑器 sed是一种流编辑器,流编辑器会在编辑器处理数据之前基于预先提供的一组规则来编辑数据流。 sed编辑器可以根据命令来处理数据流中…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...
Vite中定义@软链接
在webpack中可以直接通过符号表示src路径,但是vite中默认不可以。 如何实现: vite中提供了resolve.alias:通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...
LangFlow技术架构分析
🔧 LangFlow 的可视化技术栈 前端节点编辑器 底层框架:基于 (一个现代化的 React 节点绘图库) 功能: 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...
