当前位置: 首页 > 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;的集…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

stm32wle5 lpuart DMA数据不接收

配置波特率9600时&#xff0c;需要使用外部低速晶振...

Unity中的transform.up

2025年6月8日&#xff0c;周日下午 在Unity中&#xff0c;transform.up是Transform组件的一个属性&#xff0c;表示游戏对象在世界空间中的“上”方向&#xff08;Y轴正方向&#xff09;&#xff0c;且会随对象旋转动态变化。以下是关键点解析&#xff1a; 基本定义 transfor…...

算法打卡第18天

从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7…...

面试高频问题

文章目录 &#x1f680; 消息队列核心技术揭秘&#xff1a;从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"&#xff1f;性能背后的秘密1.1 顺序写入与零拷贝&#xff1a;性能的双引擎1.2 分区并行&#xff1a;数据的"八车道高速公路"1.3 页缓存与批量处理…...

数据库——redis

一、Redis 介绍 1. 概述 Redis&#xff08;Remote Dictionary Server&#xff09;是一个开源的、高性能的内存键值数据库系统&#xff0c;具有以下核心特点&#xff1a; 内存存储架构&#xff1a;数据主要存储在内存中&#xff0c;提供微秒级的读写响应 多数据结构支持&…...

PH热榜 | 2025-06-08

1. Thiings 标语&#xff1a;一套超过1900个免费AI生成的3D图标集合 介绍&#xff1a;Thiings是一个不断扩展的免费AI生成3D图标库&#xff0c;目前已有超过1900个图标。你可以按照主题浏览&#xff0c;生成自己的图标&#xff0c;或者下载整个图标集。所有图标都可以在个人或…...

电脑桌面太单调,用Python写一个桌面小宠物应用。

下面是一个使用Python创建的简单桌面小宠物应用。这个小宠物会在桌面上游荡&#xff0c;可以响应鼠标点击&#xff0c;并且有简单的动画效果。 import tkinter as tk import random import time from PIL import Image, ImageTk import os import sysclass DesktopPet:def __i…...

网页端 js 读取发票里的二维码信息(图片和PDF格式)

起因 为了实现在报销流程中&#xff0c;发票不能重用的限制&#xff0c;发票上传后&#xff0c;希望能读出发票号&#xff0c;并记录发票号已用&#xff0c;下次不再可用于报销。 基于上面的需求&#xff0c;研究了OCR 的方式和读PDF的方式&#xff0c;实际是可行的&#xff…...