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

看题:

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/254760.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

TCP的连接和断开详解

目录 1.TCP基础知识 1.1.TCP 头格式 1.2.TCP协议介绍 1.3.UDP协议介绍 1.4.TCP 和 UDP 区别 1.5.TCP 和 UDP 应用场景 1.6.计算机网络相关术语&#xff08;缩写&#xff09; 2.TCP 连接建立&#xff1a;三次握手 2.1.TCP 三次握手过程 2.2.三次握手原理 2.3.异常分析…

我主编的电子技术实验手册(02)——仪表与电源

本专栏是笔者主编教材&#xff08;图0所示&#xff09;的电子版&#xff0c;依托简易的元器件和仪表安排了30多个实验&#xff0c;主要面向经费不太充足的中高职院校。每个实验都安排了必不可少的【预习知识】&#xff0c;精心设计的【实验步骤】&#xff0c;全面丰富的【思考习…

机器学习系列——(二十)密度聚类

引言 在机器学习的无监督学习领域&#xff0c;聚类算法是一种关键的技术&#xff0c;用于发现数据集中的内在结构和模式。与传统的基于距离的聚类方法&#xff08;如K-Means&#xff09;不同&#xff0c;密度聚类关注于数据分布的密度&#xff0c;旨在识别被低密度区域分隔的高…

力扣刷题之旅:进阶篇(六)—— 图论与最短路径问题

力扣&#xff08;LeetCode&#xff09;是一个在线编程平台&#xff0c;主要用于帮助程序员提升算法和数据结构方面的能力。以下是一些力扣上的入门题目&#xff0c;以及它们的解题代码。 --点击进入刷题地址 引言 在算法的广阔天地中&#xff0c;图论是一个非常重要的领域。…

林浩然与杨凌芸的Java异常处理大冒险

林浩然与杨凌芸的Java异常处理大冒险 Lin Haoran and Yang Lingyun’s Java Exception Handling Adventure 在一个阳光明媚的午后&#xff0c;编程世界的英雄——林浩然和杨凌芸坐在Java王国的咖啡馆里&#xff0c;一边品尝着香醇的代码咖啡&#xff0c;一边探讨着他们的最新挑…

Excel——高级筛选匹配条件提取数据

一、筛选多条件 Q&#xff1a;筛选多个条件&#xff0c;并将筛选出的内容复制到其他区域 点击任意一个单元格 点击【数据】——【筛选】——【高级筛选】 选择【将筛选结果复制到其他位置】——在【列表区域】 鼠标选择对应的区域位置&#xff0c;条件区域一定要单独写出来&a…

ChatGPT学习第一周

&#x1f4d6; 学习目标 掌握ChatGPT基础知识 理解ChatGPT的基本功能和工作原理。认识到ChatGPT在日常生活和业务中的潜在应用。 了解AI和机器学习的基本概念 获取人工智能&#xff08;AI&#xff09;和机器学习&#xff08;ML&#xff09;的初步了解。理解这些技术是如何支撑…

Flink从入门到实践(一):Flink入门、Flink部署

文章目录 系列文章索引一、快速上手1、导包2、求词频demo&#xff08;1&#xff09;要读取的数据&#xff08;2&#xff09;demo1&#xff1a;批处理&#xff08;离线处理&#xff09;&#xff08;3&#xff09;demo2 - lambda优化&#xff1a;批处理&#xff08;离线处理&…

【机器学习】数据清洗之识别缺失点

&#x1f388;个人主页&#xff1a;甜美的江 &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;机器学习 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共同学习、交流进步…

[神奇代码岛】皮肤功能使用

前言 最近有很多人在制作地图的时候&#xff0c;因该会用到皮肤的功能&#xff0c;但是皮肤操作只知道UI操作&#xff0c;但缺点是&#xff0c;只能设置地图默认皮肤&#xff0c;根本都做不到想要的什么皮肤购买功能&#xff0c;自主穿戴功能&#xff0c;而API官方又放在非常隐…

老胡的周刊(第128期)

老胡的信息周刊[1]&#xff0c;记录这周我看到的有价值的信息&#xff0c;主要针对计算机领域&#xff0c;内容主题极大程度被我个人喜好主导。这个项目核心目的在于记录让自己有印象的信息做一个留存以及共享。 &#x1f3af; 项目 coze-discord-proxy[2] 代理 Discord-Bot 对…

微服务OAuth 2.1扩展额外信息到JWT并解析(Spring Security 6)

文章目录 一、简介二、重写UserDetailsService三、Controller解析JWT获取用户信息四、后记 一、简介 VersionJava17SpringCloud2023.0.0SpringBoot3.2.1Spring Authorization Server1.2.1Spring Security6.2.1mysql8.2.0 Spring Authorization Server 使用JWT时&#xff0c;前…

PbootCMS采集插件使用教程

这篇Pboot采集教程教你使用PbootCMS采集插件&#xff0c;自动批量采集网页文章数据&#xff0c;并发布到PbootCMS系统&#xff0c;快速丰富网站的内容。 1. 下载并安装PbootCMS采集插件 1-1&#xff09;PbootCMS采集插件免费下载&#xff1a;Pboot采集插件-PbootCMS发布模块下…

【Docker】私有仓库

目录 1.搭建 2. 上传镜像 3.拉取镜像 1.搭建 1.拉取私有仓库的镜像 docker pull registry 2.创建私有仓库容器 docker run -id --nameregistry -p 5000:5000 registry 3.打开浏览器,输入地址&#xff08;http:私有仓库服务器ip:5000/v2/_catalog&#xff09; 出现如图表示私…

如何运行心理学知识(心流)来指导工作和生活

如何运用心流来指导工作和生活 如何联系我 作者&#xff1a;鲁伟林 邮箱&#xff1a;thinking_fioa163.com或vlinyes163.com GitHub&#xff1a;https://github.com/thinkingfioa/ReadingSummary 版权声明&#xff1a;文章和记录为个人所有&#xff0c;如果转载或个人学习…

TDengine用户权限管理

Background 官方文档关于用户管理没有很详细的介绍&#xff0c;只有零碎的几条&#xff0c;这里记录下方便后面使用。官方文档&#xff1a;https://docs.taosdata.com/taos-sql/show/#show-users 1、查看用户 show users;super 1&#xff0c;表示超级用户权限 0&#xff0c;表…

MySQL用心总结

大家好&#xff0c;好久不见&#xff0c;今天笔者用心一步步写一份mysql的基础操作指南&#xff0c;欢迎各位点赞收藏 -- 启动MySQL net start mysql-- 创建Windows服务 sc create mysql binPath mysqld_bin_path(注意&#xff1a;等号与值之间有空格) mysql -h 地址 -…

kmeans聚类选择最优K值python实现

Kmeans算法中K值的确定是很重要的。 下面利用python中sklearn模块进行数据聚类的K值选择 数据集自制数据集&#xff0c;格式如下&#xff1a; 维度为3。 ①手肘法 手肘法的核心指标是SSE(sum of the squared errors&#xff0c;误差平方和)&#xff0c; 其中&#xff0c;Ci是第…

【数据分享】1929-2023年全球站点的逐年平均降水量(Shp\Excel\免费获取)

气象数据是在各项研究中都经常使用的数据&#xff0c;气象指标包括气温、风速、降水、湿度等指标&#xff0c;说到常用的降水数据&#xff0c;最详细的降水数据是具体到气象监测站点的降水数据&#xff01; 有关气象指标的监测站点数据&#xff0c;之前我们分享过1929-2023年全…

华为视频监控接入到视频监控平台 (华为网路监控摄像机IPC和华为视频节点设备VCN)

目 录 一、设备介绍 1.1 华为VCN介绍 1.2 AS-V1000视频监控平台介绍 1.3 平台服务器配置说明 二、安装、配置HW_IVS软件 2.1下载安装HW_IVS软件 2.2登录HW_IVS 2.3共享到外域 三、配置华为外域参数 3.1 PCG模块设置 3.2通信协议GBT28181配置 3.3传…