备战蓝桥杯---动态规划之经典背包问题
看题:
我们令f[i][j]为前i个物品放满容量为j的背包的最大价值。
f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i]);
我们开始全副成负无穷。f[0][0]=0;最后循环最后一行求max;
负无穷:0xc0c0c0c0;正无穷:0x3f3f3f3f
下面是v=12,n=6的图示:
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,v1,v[1002],w[1002],dp[1002][1002];
signed main(){cin>>n>>v1;for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);memset(dp,-0x3f,sizeof(dp));dp[0][0]=0;for(int i=1;i<=n;i++){for(int j=0;j<=v1;j++){if(j>=v[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);else dp[i][j]=dp[i-1][j];}}int ans=0;for(int i=0;i<=v1;i++){ans=max(ans,dp[n][i]);}cout<<ans<<endl;if(dp[n][v1]<=0) cout<<0;else cout<<dp[n][v1];
}
事实上,我们可以想象一些有体积但是没有价值的空气,显然,他不会影响最后的结果,而且它保证了对于每一行它的值递增,因此我们for循环可以省去。(不过这个前提是题目保证不一定要塞满)
加点难度:
n<=20,v<=10^9;N小,我们直接DFS
n<=100,v<=10^9:
我们可以用map来存每一行的值,对于负无穷,我们直接忽略,对于那先体积比小的大但是价值比他们小的也舍弃。
下面是代码:
#include<bits/stdc++.h>
using namespace std;
int n,v[1005],v1,w[1005],q;
map<int,int> ck[2];
int main(){cin>>n>>v1;for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);ck[0][0]=0;map<int,int>::iterator it;map<int,int>::iterator it1;for(int i=1;i<=n;i++){it=ck[(i-1)%2].begin();it1=ck[(i-1)%2].begin();while((it1->first)<v[i]&&it1!=ck[(i-1)%2].end()){ck[i%2][it1->first]=it1->second;it1++;}q=(--it1)->second;while(it!=ck[(i-1)%2].end()){if(it->first+v[i]>v1) break;if(ck[(i-1)%2].count(it->first+v[i])!=0){ck[i%2][it->first+v[i]]=max(ck[(i-1)%2][it->first]+w[i],ck[(i-1)%2][it->first+v[i]]);}else ck[i%2][it->first+v[i]]=ck[(i-1)%2][it->first]+w[i];if(q<ck[i%2][it->first+v[i]]) q=ck[i%2][it->first+v[i]];else{ck[i%2].erase(it->first+v[i]);}it++;}ck[(i-1)%2].clear();}cout<<(--ck[n%2].end())->second<<endl;
}
接下来我们看一下完全背包:
很容易,我们可得:f[i][j]=max(f[i-1][j-k*c[i]]+k*w[i])(0<=k*c[i]<=j)
其中,复杂度为k*n*v;
f[i][j]=max(f[i-1][j],f[i-1][j-c]+w,f[i-1][j-2*c]+2*w,.........)
f[i][j-c]=max(f[i-1][j-c],f[i-1][j-2*c]+w,......)
于是,f[i][j]=max(f[i][j-c]+w,f[i-1][j])
这样,我们就把复杂度->n*v;
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int n,v1,v[1005],w[1005],dp[1005];
int main(){cin>>n>>v1;memset(dp,0xc0c0c0c0,sizeof(dp));for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);dp[0]=0;for(int i=1;i<=n;i++){for(int j=v[i];j<=v1;j++){dp[j]=max(dp[j],dp[j-v[i]]+w[i]);}}int ans=0;for(int i=0;i<=v1;i++) ans=max(ans,dp[i]);cout<<ans<<endl;if(dp[v1]<0) cout<<0;else cout<<dp[v1];
}
看看多重背包:
我们可以吧一样的背包看成不一样的,这样就转化为求0/1背包,但是这样的复杂度还是和上一题类似。
我们考虑优化一下:
假如有7个物品,我们如何用跟小的数字表示它所有的方案?
我们可以采用二进制的思想--》1,2,4包,每一个方案可以组合成所有可能。
我们把数分成1,2,4,8....加上剩余的数即可。
下面是二进制压缩代码:
for(int i=1;i<=n;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);int k=1;while(k<c){v[cnt]=k*a;w[cnt++]=k*b;c-=k;k*=2;}if(c){v[cnt]=c*a;w[cnt]=c*b;}}
相关文章:
备战蓝桥杯---动态规划之经典背包问题
看题: 我们令f[i][j]为前i个物品放满容量为j的背包的最大价值。 f[i][j]max(f[i-1][j],f[i-1][j-c[i]]w[i]); 我们开始全副成负无穷。f[0][0]0;最后循环最后一行求max; 负无穷:0xc0c0c0c0;正无穷:0x3f3f3f3f 下面是v12,n6的图示ÿ…...
Go语言每日一练——链表篇(八)
传送门 牛客面试笔试必刷101题 ----------------两个链表的第一个公共结点 题目以及解析 题目 解题代码及解析 解析 这一道题使用的还是双指针算法,我们先求出两个链表的长度差n,然后定义快慢指针,让快指针先走n步,最后快慢指…...
跟着cherno手搓游戏引擎【23】项目维护、2D引擎之前的一些准备
项目维护: 修改文件结构: 头文件自己改改就好了 创建2DRendererLayer: Sandbox2D.h: #pragma once #include "YOTO.h" class Sandbox2D :public YOTO::Layer {public:Sandbox2D();virtual ~Sandbox2D() default;virtual void O…...
Redis(十三)缓存双写一致性策略
文章目录 概述示例 缓存双写一致性缓存按照操作来分,细分2种读写缓存:同步直写策略读写缓存:异步缓写策略双检加锁策略 数据库和缓存一致性更新策略先更新数据库,再更新缓存先更新缓存,再更新数据库先删除缓存…...
7 scala的类构造器
在创建对象的时候,需要调用类的构造器。Scala 提供了主构造器和辅助构造器。 1 主构造器 与 Java 一样,如果我们没有特别定义,那么 Scala 提供的默认构造器是没有参数的。 我们可以在类名后,指定构造器的参数列表,列…...
如何在 Mac 上恢复永久删除的文件:有效方法
您是否错误地从 Mac 中删除了某个文件,并且确信它已经永远消失了?好吧,你可能错了。即使您认为已永久删除计算机上的数据,仍有可能将其恢复。 在本文中,您将了解如何在 Mac 上恢复永久删除的文件,并了解增…...
Web后端开发:事务与AOP
事务管理 在学习数据库时,讲到:事务是一组操作的集合,它是一个不可分割的工作单位。事务会把所有的操作作为一个整体,一起向数据库提交或者是撤销操作请求,要么同时成功,要么同时失败。 事务的操作主要有三…...
[word] word如何打印背景和图片? #微信#其他#经验分享
word如何打印背景和图片? 日常办公中会经常要打印文件的,其实在文档的打印中也是有很多技巧的,可以按照自己的需求设定,下面给大家分享word如何打印背景和图片,一起来看看吧! 1、打印背景和图片 在默认的…...
Maven - 编译报错:程序包 XXX 不存在(多模块项目)
问题描述 编译报错:程序包 XXX 不存在(多模块项目) 原因分析 检查依赖模块 pom 文件,看是不是引入了如下插件 <plugin><groupId>org.springframework.boot</groupId><artifactId>spring-boot-maven-pl…...
Vue事件中如何使用 event 对象
在Vue中,事件处理函数常常需要获取事件触发时的相关信息,比如鼠标位置、按键信息等。而要获取这些信息,就需要使用event对象。那么在Vue的事件中如何正确使用event对象呢?接下来就来详细介绍一下。 首先,在Vue的事件中…...
Golang GC 介绍
文章目录 0.前言1.发展史2.并发三色标记清除和混合写屏障2.1 三色标记2.2 并发标记问题2.3 屏障机制Dijkstra 插入写屏障Yuasa 删除写屏障混合写屏障 3.GC 过程4.GC 触发时机5.哪里记录了对象的三色状态?6.如何观察 GC?方式1:GODEBUGgctrace1…...
决策树之scikit-learn
实例 from sklearn.datasets import load_iris from sklearn import tree import matplotlib.pyplot as plt# Load iris dataset iris load_iris() X, y iris.data, iris.target# Fit the classifier clf tree.DecisionTreeClassifier() clf clf.fit(X, y)# Plot the deci…...
Python爬虫之关系型数据库存储#5
关系型数据库是基于关系模型的数据库,而关系模型是通过二维表来保存的,所以它的存储方式就是行列组成的表,每一列是一个字段,每一行是一条记录。表可以看作某个实体的集合,而实体之间存在联系,这就需要表与…...
ANSI Escape Sequence 下落的方块
ANSI Escape Sequence 下落的方块 1. ANSI Escape 的用途 无意中发现 B站有人讲解, 完全基于终端实现俄罗斯方块。 基本想法是借助于 ANSI Escape Sequence 实现方方块的绘制、 下落动态效果等。对于只了解 ansi escape sequence 用于 log 的颜色打印的人来说&…...
Vagrant 虚拟机工具基本操作指南
Vagrant 虚拟机工具基本操作指南 #虚拟机 # #vargant# #ubuntu# 虚拟机virtualbox ,VMWare及WSL等大家都很了解了,那Vagrant是什么东西? 它是一组命令行工具,可以象Docker管理容器一样管理虚拟机,这样快速创…...
中年低端中产程序员从西安出发到海南三亚低成本吃喝万里行:西安-南宁-湛江-雷州-徐闻-博鳌-陵水-三亚-重庆-西安
文章大纲 旅途规划来回行程的确定南宁 - 北海 - 湛江轮渡成为了最终最大的不确定性!感谢神州租车气温与游玩地点总体花费 游玩过程出发时间:Day1-1月25日星期四,西安飞南宁路途中:Day2-1月26日星期五,南宁-湛江-住雷州…...
企业级Spring boot项目 配置清单
目录 一、服务基础配置 二、配置数据库数据源 三、配置缓存 四、配置日志 五、配置统一异常处理 六、配置swagger文档 七、配置用户登录模块 八、配置websocket 九、配置定时任务 十、配置文件服务器 十一、配置Nacos 十二、配置项目启动数据库默认初始化(liquibas…...
WordPress函数wptexturize的介绍及用法示例,字符串替换为HTML实体
在查看WordPress你好多莉插件时发现代码中使用了wptexturize()函数用来随机输出一句歌词,下面boke112百科就跟大家一起来学习一下WordPress函数wptexturize的介绍及用法示例。 WordPress函数wptexturize介绍 wptexturize( string $text, bool $reset false ): st…...
【Iceberg学习三】Reporting和Partitioning原理
Metrics Reporting Type of Reports 从 1.1.0 版本开始,Iceberg 支持 MetricsReporter 和 MetricsReport API。这两个 API 允许表达不同的度量报告,并支持一种可插拔的方式来报告这些报告。 ScanReport(扫描报告) 扫描报告&am…...
肯尼斯·里科《C和指针》第12章 使用结构和指针(1)链表
只恨当时学的时候没有读到这本书,,,,,, 12.1 链表 有些读者可能还不熟悉链表,这里对它作一简单介绍。链表(linked list)就一些包含数据的独立数据结构(通常称为节点)的集…...
Xray 工具笔记
Xray 官方文档 扫描单个url(非爬虫) 并输出文件(不同文件类型) .\xray.exe webscan --url 10.0.0.6:8080 --text-output result.txt --json-output result.json --html-output report.html默认启动所以内置插件 ,指定…...
Linux环境下配置HTTP代理服务器教程
大家好,我是你们可爱的Linux小助手!今天,我将带你们一起探索如何在Linux环境下配置一个HTTP代理服务器。请注意,这不是一次火箭科学的实验,而是一次简单而有趣的冒险。 首先,我们需要明确什么是HTTP代理服…...
JavaEE作业-实验三
目录 1 实验内容 2 实验要求 3 思路 4 核心代码 5 实验结果 1 实验内容 简单的线上图书交易系统的web层 2 实验要求 ①采用SpringMVC框架,采用REST风格 ②要求具有如下功能:商品分类、订单、购物车、库存 ③独立完成,编写实验报告 …...
K8S容器挂了后重启状态正常,但应用无法访问排查处理
K8S容器挂了后重启状态正常,但应用无法访问排查处理 背景: 应用迁移K8S后因POD OOM挂了后重启,集群上POD状态正常,但应用无法访问。 排查: 查看应用日志,是启动时调用特权账号管理系统超时,…...
问题:老年人心理健康维护与促进的原则为________、________、发展原则。 #媒体#知识分享
问题:老年人心理健康维护与促进的原则为________、________、发展原则。 参考答案如图所示...
【超高效!保护隐私的新方法】针对图像到图像(l2l)生成模型遗忘学习:超高效且不需要重新训练就能从生成模型中移除特定数据
针对图像到图像生成模型遗忘学习:超高效且不需要重新训练就能从生成模型中移除特定数据 提出背景如何在不重训练模型的情况下从I2I生成模型中移除特定数据? 超高效的机器遗忘方法子问题1: 如何在图像到图像(I2I)生成模型中进行高效…...
Transformer的PyTorch实现之若干问题探讨(二)
在《Transformer的PyTorch实现之若干问题探讨(一)》中探讨了Transformer的训练整体流程,本文进一步探讨Transformer训练过程中teacher forcing的实现原理。 1.Transformer中decoder的流程 在论文《Attention is all you need》中࿰…...
解释Python中的GIL(全局解释器锁)及其影响。描述Python中的垃圾回收机制。Python中的类变量和实例变量有什么区别
解释Python中的GIL(全局解释器锁)及其影响 Python中的GIL(全局解释器锁)是CPython解释器中的一个机制,用于同步线程的执行。GIL确保任何时候只有一个线程在执行Python字节码。这意味着,即使在多核或多处理器…...
Appium使用初体验之参数配置,简单能够运行起来
一、服务器配置 Appium Server配置与Appium Server GUI(可视化客户端)中的配置对应,尤其是二者如果不在同一台机器上,那么就需要配置Appium Server GUI所在机器的IP(Appium Server GUI的HOST也需要配置本机IP…...
Java:JDK8新特性(Stream流)、File类、递归 --黑马笔记
一、JDK8新特性(Stream流) 接下来我们学习一个全新的知识,叫做Stream流(也叫Stream API)。它是从JDK8以后才有的一个新特性,是专业用于对集合或者数组进行便捷操作的。有多方便呢?我们用一个案…...
【Unity ShaderGraph】| 物体靠近时局部溶解,根据坐标控制溶解的位置【文末送书】
前言 【Unity ShaderGraph】| 物体靠近时局部溶解,根据坐标控制溶解的位置一、效果展示二、根据坐标控制溶解的位置,物体靠近局部溶解三、应用实例👑评论区抽奖送书 前言 本文将使用ShaderGraph制作一个根据坐标控制溶解的位置,物…...
测试OpenSIPS3.4.3的lua模块
这几天测试OpenSIPS3.4.3的lua模块,记录如下: 有bug,但能用 但现实世界就是这样,总是不完美的,发现之后马上提了issue 下面这段代码运行报错: function func1(msg) xlog("ERR","…...
【机器学习】数据清洗之处理缺失点
🎈个人主页:甜美的江 🎉欢迎 👍点赞✍评论⭐收藏 🤗收录专栏:机器学习 🤝希望本文对您有所裨益,如有不足之处,欢迎在评论区提出指正,让我们共同学习、交流进步…...
Linux 命令行的世界 :2.文件系统中跳转
我们需要学习的第一件事(除了打字之外)是如何在 Linux 文件系统中跳转。在这一章节中,我们将介绍以下命令:pwd 打印出当前工作目录名 cd 更改目录 ls 列出目录内容 Linux以分层目录结构来组织所有文件。这就意味着所有文件…...
R语言:箱线图绘制(添加平均值趋势线)
箱线图绘制 1. 写在前面2.箱线图绘制2.1 相关R包导入2.2 数据导入及格式转换2.3 ggplot绘图 1. 写在前面 今天有时间把之前使用过的一些代码和大家分享,其中箱线图绘制我认为是非常有用的一个部分。之前我是比较喜欢使用origin进行绘图,但是绘制的图不太…...
Open3D 模型切片
目录 一、算法原理1、算法过程2、主要函数二、代码实现三、结果展示1、原始数据2、切片结果本文由CSDN点云侠原创,原文链接。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫与GPT。 一、算法原理...
KtConnect 本地连接连接K8S工具
KT Connect简介 Kt Connect (Kubernetes Developer Tool)是一个阿里开源、轻量级的面向 Kubernetes 用户的开发测试环境治理辅助工具。其核心是通过建立本地到集群以及集群到本地的双向通道。 1.阿里开源,轻量级, 2. 安装快捷简单…...
【Java万花筒】数据的安全钥匙:Java的加密与保护方法
编码的盾牌:Java开发人员的安全性武器库 前言 在当今数字化时代,保护用户数据和信息的安全已成为开发人员的首要任务。无论是在Web应用程序开发还是安全测试中,加密和安全性都是至关重要的。本文将介绍六个Java库和工具,它们为开…...
【Java多线程案例】实现阻塞队列
1. 阻塞队列简介 1.1 阻塞队列概念 阻塞队列:是一种特殊的队列,具有队列"先进先出"的特性,同时相较于普通队列,阻塞队列是线程安全的,并且带有阻塞功能,表现形式如下: 当队列满时&…...
【制作100个unity游戏之24】unity制作一个3D动物AI生态系统游戏3(附项目源码)
最终效果 文章目录 最终效果系列目录前言随着地面法线旋转在地形上随机生成动物不同部位颜色不同最终效果源码完结系列目录 前言 欢迎来到【制作100个Unity游戏】系列!本系列将引导您一步步学习如何使用Unity开发各种类型的游戏。在这第24篇中,我们将探索如何用unity制作一…...
home work day5
第四章 堆与拷贝构造函数 一 、程序阅读题 1、给出下面程序输出结果。 #include <iostream.h> class example {int a; public: example(int b5){ab;} void print(){aa1;cout <<a<<"";} void print()const {cout<<a<<endl;} …...
c#安全-nativeAOT
文章目录 前记AOT测试反序列化Emit 前记 JIT\AOT JIT编译器(Just-in-Time Complier),AOT编译器(Ahead-of-Time Complier)。 AOT测试 首先编译一段普通代码 using System; using System.Runtime.InteropServices; namespace co…...
【Java】案例:检测MySQL是否存在某数据库,没有则创建
1.代码 package hello; import java.sql.*;public class CeShi {//定义基本数据static final String JDBC_DRIVER "com.mysql.cj.jdbc.Driver";static final String DB_URL "jdbc:mysql://localhost/";static final String USER "your_username&q…...
内网渗透靶场02----Weblogic反序列化+域渗透
网络拓扑: 攻击机: Kali: 192.168.111.129 Win10: 192.168.111.128 靶场基本配置:web服务器双网卡机器: 192.168.111.80(模拟外网)10.10.10.80(模拟内网)域成员机器 WIN7PC192.168.…...
[嵌入式系统-9]:C语言程序调用汇编语言程序的三种方式
目录 1. 使用函数声明和函数调用: 2. 使用汇编内联(Inline Assembly): 3. 使用汇编代码文件和链接器: C语言程序可以调用汇编程序的方式有多种,下面列举了几种常见的方式: 1. 使用函数声明和…...
备战蓝桥杯---搜索(完结篇)
再看一道不完全是搜索的题: 解法1:贪心并查集: 把冲突事件从大到小排,判断是否两个在同一集合,在的话就返回,不在的话就合并。 下面是AC代码: #include<bits/stdc.h> using namespace …...
深入浅出:Golang的Crypto/SHA256库实战指南
深入浅出:Golang的Crypto/SHA256库实战指南 介绍crypto/sha256库概览主要功能应用场景库结构和接口实例 基础使用教程字符串哈希化文件哈希化处理大型数据 进阶使用方法增量哈希计算使用Salt增强安全性多线程哈希计算 实际案例分析案例一:安全用户认证系…...
Unity_ShaderGraph节点问题
Unity_ShaderGraph节点问题 Unity版本:Unity2023.1.19 为什么在Unity2023.1.19的Shader Graph中找不见PBR Master节点? 以下这个PBR Maste从何而来?...
Java集合 Collection接口
这里写目录标题 集合Collection接口创建一个性表增加元素删除元素修改元素判断元素遍历集合实例判断元素是否存在 集合 Java中的Collection接口是集合类的一个顶级接口,它定义了一些基本的操作,如添加、删除、查找等。Collection接口主要有以下几个常用…...
C# Task的使用
C#中的Task类是.NET框架中用于实现异步编程的核心组件之一,它在.NET Framework 4及更高版本以及.NET Core中广泛使用。Task对象代表一个异步操作,并提供了跟踪异步操作状态、获取结果和处理完成通知的方法。 Task 类提供了对异步操作的封装,…...