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编辑器可以根据命令来处理数据流中…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
【Linux】Linux安装并配置RabbitMQ
目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的,需要先安…...
【实施指南】Android客户端HTTPS双向认证实施指南
🔐 一、所需准备材料 证书文件(6类核心文件) 类型 格式 作用 Android端要求 CA根证书 .crt/.pem 验证服务器/客户端证书合法性 需预置到Android信任库 服务器证书 .crt 服务器身份证明 客户端需持有以验证服务器 客户端证书 .crt 客户端身份…...
2025年低延迟业务DDoS防护全攻略:高可用架构与实战方案
一、延迟敏感行业面临的DDoS攻击新挑战 2025年,金融交易、实时竞技游戏、工业物联网等低延迟业务成为DDoS攻击的首要目标。攻击呈现三大特征: AI驱动的自适应攻击:攻击流量模拟真实用户行为,差异率低至0.5%,传统规则引…...
