01背包问题 刷题笔记

思路 dp
用f[i][j]来表示当体积为j时 考虑前i件物品可以获得的 最大值
记住f[i][j]本身是个价“价值”
考虑两种状态 是否将第i件物品放入背包里面
将背包的体积从小到大递增来进行考虑
首先 考虑条件 如果当前增加的体积放不下下一件物品
则该体积 可以获得的最大值可以直接继承上一个f[i-1][j]
如果可以放下 则比较 放入与不放入谁获得的值较大
即 f[i-1][j]与f[i-1][j-v[i]]+w[i]比较
//-v[i]是为了减去放入后的背包体积
加w[i]是为了加上放入后获得的价值
每一次存下的 都是基于考虑到当前物品 的最优选择
比方说 前面已经进行了i件物品的选择
获得了一个基于i件物品的最大值
这时候 第i+1件物品突然出现 体积为1,价值1000000;
那么当背包体积只有1时的最大值会立刻被更新成100000;
此时仍然是最优选择
代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=1010;
int f[N][N];
int w[N],v[N];
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(j<v[i]){
f[i][j]=f[i-1][j];
}else{
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
}
}
}
cout<<f[n][m];
return 0;
}
优化思路
二维到一维
我们发现 考虑第i件物品时的最大值来自前面一层i-1件物品的最大值
也就是说 所有的当前层 都只来自上一层的最大值
而上上层已经不重要了
因此有没有可能直接删掉层数记录
观察发现f[i][]是从f[i-1][]这一层更新出来的
此时我们直接删除i
只使用j
观察式子f[j-v[i]]+w[i]
也就是说 如果我们逆序更新的话 需要使用和比较的数是j-v[i]
这个数是绝对小于j的 如果将j从m往0更新
保证了更新时只有大于等于j的数被覆盖掉了
而我们需要用的 j-v[i]则被保留下来
举例
如果我们逆序更新的话
假设 原来 f[j](1-5)是
1 2 5 7 9
然后我们逆序更新
for(int i=0;i<n;i++){
for(int j=m;j>=v[i];j--){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
假设 此时j=5,v[i]=2, f[j-v[i]]+w[i]=11那么
我们和上一个f[3]比较 比较完了以后将上一个f[5]覆盖掉
此时f[j](1-5)的情况为
1 2 5 7 11
然后当j=4;
v[i]=1;
f[j-v[i]]+w[i]=9;
即我们需要用的是f[3]
此时f[3]并没有被污染
执行以后
f[j](1-5)的情况为
1 2 5 9 11
以此类推我们的目的达到了
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N];
int w[N],v[N];
int j[N];
int n,m;
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
//int x,y;
cin>>v[i]>>w[i];
//v[i]=x;
//w[i]=y;
}
for(int i=0;i<n;i++){
for(int j=m;j>=v[i];j--){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m];
return 0;
相关文章:
01背包问题 刷题笔记
思路 dp 用f[i][j]来表示当体积为j时 考虑前i件物品可以获得的 最大值 记住f[i][j]本身是个价“价值” 考虑两种状态 是否将第i件物品放入背包里面 将背包的体积从小到大递增来进行考虑 首先 考虑条件 如果当前增加的体积放不下下一件物品 则该体积 可以获得的最大值可以直接…...
docker安装包(Linux和windows)
Linux——docker-20.10.9.tgz 网盘地址:链接:https://pan.baidu.com/s/1T3qfVZ-uT-vMAo8w6heTMw 提取码:qu85 windows——docker19.03.1 链接:https://pan.baidu.com/s/1mK6hqhkGCBs6tdBHJxrdPw 提取码:4dkj...
RabbitMQ 安装使用
文章目录 RabbitMQ 安装使用安装下载 Erlang下载 RabbitMQ 的服务安装好后看是否有 RabbitMQ 的服务开启管理 UIRabbitMQ 端口使用一览图 使用输出最简单的 Hello World!生产者定义消费者消费消息小拓展 RabbitMQ 安装使用 安装 下载 Erlang RabbitMQ 是用这个语…...
echarts x轴名称过长tip显示全称
xAxis的axisLabel的内容如下: axisLabel: { rotate: -45, color: document.body.className.indexOf(custom-f4c46d) > -1 ? #fff : #343434, // 显示省略号操作(第一步) formatter: function (value) { var val if (value.length >…...
js和css阻塞问题
面试常见问题 css 加载会不会阻塞 js 的加载?(不会)css 加载会不会阻塞 js 的执行?(会)css 加载会不会阻塞 DOM 的解析?(不会)css 加载会不会阻塞 DOM 的渲染࿱…...
MySQL 的基础操作
数据库的基础操作 1. 库操作2. 表的操作3. 数据类型 数据库是现代应用程序中至关重要的组成部分,通过数据库管理系统(DBMS)存储和管理数据。 1. 库操作 创建数据库 创建数据库是开始使用数据库的第一步。下面是一些常见的创建数据库的示例&a…...
【python进阶篇】面向对象编程(1)
面向对象编程——Object Oriented Programming,简称OOP,是一种程序设计思想。OOP把对象作为程序的基本单元,一个对象包含了数据和操作数据的函数。 在Python中,所有数据类型都可以视为对象,当然也可以自定义对象。自定…...
力扣面试经典150 —— 6-10题
力扣面试经典150题在 VScode 中安装 LeetCode 插件即可使用 VScode 刷题,安装 Debug LeetCode 插件可以免费 debug本文使用 python 语言解题,文中 “数组” 通常指 python 列表;文中 “指针” 通常指 python 列表索引 文章目录 6. [中等] 轮转…...
[密码学]入门篇——加密方式
一、概述 加密方法主要分为两大类: 单钥加密(private key cryptography):加密和解密过程都用同一套密码双钥加密(public key cryptography):加密和解密过程用的是两套密码 历史上,…...
构建前后端分离项目常用的代码
构建前后端分离项目常用的代码 1.代码生成器 import com.baomidou.mybatisplus.generator.FastAutoGenerator;import com.baomidou.mybatisplus.generator.config.OutputFile;import com.baomidou.mybatisplus.generator.engine.FreemarkerTemplateEngine;import java.util.…...
2575. 找出字符串的可整除数组(Go语言)
https://leetcode.cn/problems/find-the-divisibility-array-of-a-string/ 在看题解之前,我的代码是以下这样: package mainimport ("fmt" )func main() {fmt.Println(divisibilityArray("998244353", 3)) }func divisibilityArray…...
Redis与 Memcache区别
Redis与 Memcache区别 1 , Redis 和 Memcache 都是将数据存放在内存中,都是内存数据库。不过 Memcache 还可用于缓存 其他东西,例如图片、视频等等。 2 , Memcache 仅支持key-value结构的数据类型,Redis不仅仅支持简单的key-value类型的数据&…...
#QT(智能家居界面-界面切换)
1.IDE:QTCreator 2.实验 3.记录 (1)创建一个新界面(UI界面) (2)可以看到新加入一个ui文件,双击打开,设置窗口大小与登录界面一致 (3)加入几个PUS…...
js拓展-内置对象
目录 1. 数组对象 1.1 数组的四种方式 1.2 JS中数组的特点 1.3 常用方法 2. 日期对象 2.1 日期对象的创建 2.2 日期对象的方法 2.3 案例:输出现在的时间 3. 全局对象 3.1 字符串转换成数字类型 3.2 编码解码函数 1. 数组对象 注:数组在JS中是一…...
【李沐精读系列】GPT、GPT-2和GPT-3论文精读
论文: GPT:Improving Language Understanding by Generative Pre-Training GTP-2:Language Models are Unsupervised Multitask Learners GPT-3:Language Models are Few-Shot Learners 参考:GPT、GPT-2、GPT-3论文精读…...
Libevent的使用及reactor模型
Libevent 是一个用C语言编写的、轻量级的开源高性能事件通知库,主要有以下几个亮点:事件驱动( event-driven),高性能;轻量级,专注于网络,不如 ACE 那么臃肿庞大;源代码相当精炼、易读…...
查看Linux服务器配置
# chkconfig --list # 列出所有系统服务 # chkconfig --list | grep on # 列出所有启动的系统服务 # ifconfig # 查看所有网络接口的属性 # iptables -L # 查看防火墙设置 # route -n # 查看路由表 # netstat -lntp # 查看所有监听端口 # netstat -antp # 查看所有已经建立的连…...
【机器学习】包裹式特征选择之递归特征添加法
🎈个人主页:豌豆射手^ 🎉欢迎 👍点赞✍评论⭐收藏 🤗收录专栏:机器学习 🤝希望本文对您有所裨益,如有不足之处,欢迎在评论区提出指正,让我们共同学习、交流进…...
解决cs不能生成Linux木马的问题
要解决的问题:众所周知,msf上面的shell或者是其他的shell想反弹给cs默认情况下是只支持windows的,因为cs的监听模块默认没有linux的,但是有些主机就是用linux搭建的,这可怎么办呢。就要用到一个插件CrossC2。 下载插件…...
vue3组件通信方式
不管是vue2还是vue3,组件通信方式很重要,不管是项目还是面试都是经常用到的知识点。 vue2组件通信方式 props:可以实现父子组件、子父组件、甚至兄弟组件通信 自定义事件:可以实现子父组件通信 全局事件总线$bus:可以实现任意组件通信 pubsub:发布订阅模式实现任意组件通信…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
jmeter聚合报告中参数详解
sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample(样本数) 表示测试中发送的请求数量,即测试执行了多少次请求。 单位,以个或者次数表示。 示例:…...
