当前位置: 首页 > news >正文

备战蓝桥杯---动态规划之经典背包问题

看题:

我们令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;}}

相关文章:

备战蓝桥杯---动态规划之经典背包问题

看题&#xff1a; 我们令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; 负无穷&#xff1a;0xc0c0c0c0;正无穷&#xff1a;0x3f3f3f3f 下面是v12,n6的图示&#xff…...

Go语言每日一练——链表篇(八)

传送门 牛客面试笔试必刷101题 ----------------两个链表的第一个公共结点 题目以及解析 题目 解题代码及解析 解析 这一道题使用的还是双指针算法&#xff0c;我们先求出两个链表的长度差n&#xff0c;然后定义快慢指针&#xff0c;让快指针先走n步&#xff0c;最后快慢指…...

跟着cherno手搓游戏引擎【23】项目维护、2D引擎之前的一些准备

项目维护&#xff1a; 修改文件结构&#xff1a; 头文件自己改改就好了 创建2DRendererLayer&#xff1a; Sandbox2D.h: #pragma once #include "YOTO.h" class Sandbox2D :public YOTO::Layer {public:Sandbox2D();virtual ~Sandbox2D() default;virtual void O…...

Redis(十三)缓存双写一致性策略

文章目录 概述示例 缓存双写一致性缓存按照操作来分&#xff0c;细分2种读写缓存&#xff1a;同步直写策略读写缓存&#xff1a;异步缓写策略双检加锁策略 数据库和缓存一致性更新策略先更新数据库&#xff0c;再更新缓存先更新缓存&#xff0c;再更新数据库先删除缓存&#xf…...

7 scala的类构造器

在创建对象的时候&#xff0c;需要调用类的构造器。Scala 提供了主构造器和辅助构造器。 1 主构造器 与 Java 一样&#xff0c;如果我们没有特别定义&#xff0c;那么 Scala 提供的默认构造器是没有参数的。 我们可以在类名后&#xff0c;指定构造器的参数列表&#xff0c;列…...

如何在 Mac 上恢复永久删除的文件:有效方法

您是否错误地从 Mac 中删除了某个文件&#xff0c;并且确信它已经永远消失了&#xff1f;好吧&#xff0c;你可能错了。即使您认为已永久删除计算机上的数据&#xff0c;仍有可能将其恢复。 在本文中&#xff0c;您将了解如何在 Mac 上恢复永久删除的文件&#xff0c;并了解增…...

Web后端开发:事务与AOP

事务管理 在学习数据库时&#xff0c;讲到&#xff1a;事务是一组操作的集合&#xff0c;它是一个不可分割的工作单位。事务会把所有的操作作为一个整体&#xff0c;一起向数据库提交或者是撤销操作请求&#xff0c;要么同时成功&#xff0c;要么同时失败。 事务的操作主要有三…...

[word] word如何打印背景和图片? #微信#其他#经验分享

word如何打印背景和图片&#xff1f; 日常办公中会经常要打印文件的&#xff0c;其实在文档的打印中也是有很多技巧的&#xff0c;可以按照自己的需求设定&#xff0c;下面给大家分享word如何打印背景和图片&#xff0c;一起来看看吧&#xff01; 1、打印背景和图片 在默认的…...

Maven - 编译报错:程序包 XXX 不存在(多模块项目)

问题描述 编译报错&#xff1a;程序包 XXX 不存在&#xff08;多模块项目&#xff09; 原因分析 检查依赖模块 pom 文件&#xff0c;看是不是引入了如下插件 <plugin><groupId>org.springframework.boot</groupId><artifactId>spring-boot-maven-pl…...

Vue事件中如何使用 event 对象

在Vue中&#xff0c;事件处理函数常常需要获取事件触发时的相关信息&#xff0c;比如鼠标位置、按键信息等。而要获取这些信息&#xff0c;就需要使用event对象。那么在Vue的事件中如何正确使用event对象呢&#xff1f;接下来就来详细介绍一下。 首先&#xff0c;在Vue的事件中…...

Golang GC 介绍

文章目录 0.前言1.发展史2.并发三色标记清除和混合写屏障2.1 三色标记2.2 并发标记问题2.3 屏障机制Dijkstra 插入写屏障Yuasa 删除写屏障混合写屏障 3.GC 过程4.GC 触发时机5.哪里记录了对象的三色状态&#xff1f;6.如何观察 GC&#xff1f;方式1&#xff1a;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

关系型数据库是基于关系模型的数据库&#xff0c;而关系模型是通过二维表来保存的&#xff0c;所以它的存储方式就是行列组成的表&#xff0c;每一列是一个字段&#xff0c;每一行是一条记录。表可以看作某个实体的集合&#xff0c;而实体之间存在联系&#xff0c;这就需要表与…...

ANSI Escape Sequence 下落的方块

ANSI Escape Sequence 下落的方块 1. ANSI Escape 的用途 无意中发现 B站有人讲解&#xff0c; 完全基于终端实现俄罗斯方块。 基本想法是借助于 ANSI Escape Sequence 实现方方块的绘制、 下落动态效果等。对于只了解 ansi escape sequence 用于 log 的颜色打印的人来说&…...

Vagrant 虚拟机工具基本操作指南

Vagrant 虚拟机工具基本操作指南 ​#虚拟机 #​ ​#vargant#​ ​#ubuntu#​ ‍ 虚拟机virtualbox ,VMWare及WSL等大家都很了解了&#xff0c;那Vagrant是什么东西&#xff1f; 它是一组命令行工具&#xff0c;可以象Docker管理容器一样管理虚拟机&#xff0c;这样快速创…...

中年低端中产程序员从西安出发到海南三亚低成本吃喝万里行:西安-南宁-湛江-雷州-徐闻-博鳌-陵水-三亚-重庆-西安

文章大纲 旅途规划来回行程的确定南宁 - 北海 - 湛江轮渡成为了最终最大的不确定性&#xff01;感谢神州租车气温与游玩地点总体花费 游玩过程出发时间&#xff1a;Day1-1月25日星期四&#xff0c;西安飞南宁路途中&#xff1a;Day2-1月26日星期五&#xff0c;南宁-湛江-住雷州…...

企业级Spring boot项目 配置清单

目录 一、服务基础配置 二、配置数据库数据源 三、配置缓存 四、配置日志 五、配置统一异常处理 六、配置swagger文档 七、配置用户登录模块 八、配置websocket 九、配置定时任务 十、配置文件服务器 十一、配置Nacos 十二、配置项目启动数据库默认初始化(liquibas…...

WordPress函数wptexturize的介绍及用法示例,字符串替换为HTML实体

在查看WordPress你好多莉插件时发现代码中使用了wptexturize()函数用来随机输出一句歌词&#xff0c;下面boke112百科就跟大家一起来学习一下WordPress函数wptexturize的介绍及用法示例。 WordPress函数wptexturize介绍 wptexturize( string $text, bool $reset false ): st…...

【Iceberg学习三】Reporting和Partitioning原理

Metrics Reporting Type of Reports 从 1.1.0 版本开始&#xff0c;Iceberg 支持 MetricsReporter 和 MetricsReport API。这两个 API 允许表达不同的度量报告&#xff0c;并支持一种可插拔的方式来报告这些报告。 ScanReport&#xff08;扫描报告&#xff09; 扫描报告&am…...

肯尼斯·里科《C和指针》第12章 使用结构和指针(1)链表

只恨当时学的时候没有读到这本书&#xff0c;&#xff0c;&#xff0c;&#xff0c;&#xff0c;&#xff0c; 12.1 链表 有些读者可能还不熟悉链表&#xff0c;这里对它作一简单介绍。链表(linked list)就一些包含数据的独立数据结构&#xff08;通常称为节点&#xff09;的集…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...

libfmt: 现代C++的格式化工具库介绍与酷炫功能

libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库&#xff0c;提供了高效、安全的文本格式化功能&#xff0c;是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全&#xff1a…...