蓝桥杯DP算法——背包问题(C++)

目录

一、01背包问题

二、完全背包问题

三、多重背包问题

四、多重背包问题(优化版)

五、分组背包问题


一、01背包问题

01背包问题就是有N件物品,一个空间大小为V的背包,每个物品只能使用一次,使得背包中所装物品的价值总和最大。

  如图所示使用一个二维数组来存放从前i个物品中取,总体积不超过j的包中价值最大值。

 根据图二所示,我们可以将每次dp到的情况分为两种,一种是选择第 i 件物品,另一种是不选择第 i 件物品。

  • (不含 i )就是从0~i-1中选择体积不超过 j 的物品,也就是f(i-1,j)
  • (含 i )即从 1 ~ i 中选,包含 i,且总体积不超过 j。可以先把第 i 个物品拿出来,即从第 1 ~ i-1中选,且总体积不超过 j-v[i],也就是f(i-1,j-v_{i})+w_{i}

最终:f[ i ][ j ] = max(f[ i-1 ][ j ], f[i-1][j-v[ i ]] +w[ i ]

例题:https://www.acwing.com/problem/content/2/

朴素做法: 

#include<iostream>
using namespace std;
const int N=1010;
int v[N],w[N];
int f[N][N];int main()
{int n,m;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++){f[i][j]=f[i-1][j];if(j>=v[i])//可以装的下{f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);}}}cout<<f[n][m];return 0;
}

优化: 

 f[i] 只用到了 f[i-1] 这一层,即 f[i-2] 到 f[0] 对 f[i] 是没有用的,所以第二层循环可以直接从 v[i] 开始

for (int i = 1; i <= n; i++) {for (int j = v[i]; j <= m; j++) {f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);}
}

 从二维优化成一维(空间优化)

如果直接删除掉 f[i] 这一维即

f[j] = max(f[j], f[j-v[i]] + w[i]);

但是这样直接删掉是错误,因为j是递增的。

原式:f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);

改成一维:f[j] = max(f[j], f[j - v[i]] + w[i]);

由于 f[i][] 只跟上一状态(f[i - 1][])有关 上面两个式子 :这一状态(左) = 上一状态(右)

即 f[i][j] 是由 f[i - 1][j - v[i]] 推出来的 现在进行空间优化,那么必须要保证 f[j] 要由 f[j - v[i]] 推出来的。

如果j层循环是递增的,则相当于 f[i][j] 变得是由 f[i][j - v[i]] 推出来的, 而不是 f[i - 1][j - v[i]] 推出来的。

优化后代码:

#include<iostream>
using namespace std;
const int N=1010;
int v[N],w[N];
int f[N];int main()
{int n,m;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=m;j>=v[i];j--){f[j]=max(f[j],f[j-v[i]]+w[i]);}}cout<<f[m];return 0;
}

二、完全背包问题

完全背包不同于01背包的是,每件物品都是无限使用的。

如图所示,与01背包相似的是每次选择0,1,2,3,4,5,....k个

不选时仍是 f[ i-1][ j ]

选择k件时是 f[ i-1][ j-k*v[i]] +k*w[i]

也就是:

                                                         f[ i-1][ j-k*v[i]] +k*w[i]

 例题:https://www.acwing.com/problem/content/3/

朴素写法: 

#include<iostream>
using namespace std;const int N=1010;
int n,m;
int v[N],w[N],f[N][N];int main()
{cin>>n>>m;for(int i=i;i<=n;i++) scanf("%d%d",&v[i],&w[i]);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int k=0;k*v[i]<=j;k++){f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);}}}cout<<f[n][m];return 0;
}

优化:

在对完全背包问题优化时,我们由图公式可知f[i][j]可以简化为max(f[i-1][j],f[i][j-v]+w)

优化后代码:

#include <iostream>
#include <algorithm>using namespace std;const int N=1010;
int f[N];
int v[N],w[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=v[i];j<=m;j++){f[j]=max(f[j],f[j-v[i]]+w[i]);}}cout<<f[m];return 0;
}

三、多重背包问题

多重背包问题相较于之前的问题就是每个物品是有限s个。 

例题:https://www.acwing.com/problem/content/4/

#include<iostream>
using namespace std;
const int N=110;int n,m;
int s[N],v[N],w[N];
int f[N][N];int main()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){for(int k=0;k<=s[i]&&j>=(k*v[i]);k++){f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);}}}cout<<f[n][m];return 0;
}

四、多重背包问题(优化版)

首先我们以之前完全背包问题的优化方法尝试使用另一个表达式来代替,但是结果如图所示,不是很好解决。 

二进制法优化:二进制优化的方法在于使用二进制的表示方式来代替每个物品的个数,当某件物品的个数很多的时候无需从1遍历循环到n,可以将其分解成log_{_{2}^{}}^{n}个位权来表示。

为了方便理解举个例子:

如果要拿1001次苹果,传统就是要拿1001次;二进制的思维,就是拿7个箱子就行(分别是装有512、256、128、64、32、8、1个苹果的这7个箱子),这样一来,1001次操作就变成7次操作就行了。

但是要注意的一点是如果某件物品的个数不是二次幂减一,就将前一位的值与s差值记为下一个位权。这样就可以表示0~s之内的所有数了。

然后就将问题分解成为了,01背包问题。

例题:https://www.acwing.com/problem/content/5/

#include<iostream>
using namespace std;const int N=11010,M=2010;
int v[N],w[N];
int f[N];int main()
{int n,m;cin>>n>>m;int cnt=0;while(n--)//初始化v[] w[]{int a,b,s;cin>>a>>b>>s;int k=1;while(k<=s){cnt++;v[cnt]=a*k;w[cnt]=b*k;s-=k;k*=2;}if(s>0){cnt++;v[cnt]=a*s;w[cnt]=b*s;}}n=cnt;//01背包for(int i=1;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;
}

五、分组背包问题

分组背包问题的不同于之前背包问题的地方在于分组背包是将物品分成几组,然后再在每组里面选择一个物品,并且每组只能选择一个物品。

这里的dp状态计算与之前的也有所不同,这里表示的是第i组选哪一个,f[i-1][j]是表示不选择这一组的物品,f[i-1][j-v[i,k]]+w[i,k]表示的是这一组中选择哪一个。 

例题: https://www.acwing.com/problem/content/9/

#include<iostream>
using namespace std;const int N=110;
int n,m;
int s[N],v[N][N],w[N][N];
int f[N];int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>s[i];for(int j=1;j<=s[i];j++){cin>>v[i][j]>>w[i][j];}}for(int i=1;i<=n;i++){for(int j=m;j>=0;j-- ){for(int k=0;k<=s[i];k++){if(v[i][k]<=j){f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);}}}}cout<<f[m];return 0;
}

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

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

相关文章

2019年江苏省职教高考计算机技能考试——一道程序改错题的分析

题目&#xff1a;函数将str字符串中的5个数字字符串转换为整数&#xff0c;并保存在二维数组m的最后一行&#xff0c;各元素为3、-4、16、18、6。并经函数move处理后&#xff0c;运行结果如下&#xff1a; 18 6 3 -4 16 16 18 6 3 -4 -4 16 …

【AIGC】Stable Diffusion之模型微调工具

推荐一款好用的模型微调工具&#xff0c;cybertron furnace 是一个lora训练整合包&#xff0c;提供训练 lora 模型的工具集或环境。集成环境包括必要的依赖项和配置文件、预训练脚本&#xff0c;支持人物、二次元、画风、自定义lora的训练&#xff0c;以简化用户训练 lora 模型…

【Linux】软件包管理器 yum | vim编辑器

前言: 软件包管理器 yum和vim编辑器讲解 文章目录 软件包管理器 yum编辑器-vim四种模式普通模式批量化注释和批量化去注释末行模式临时文件 软件包管理器 yum yum&#xff08;Yellowdog Updater, Modified&#xff09;是一个在基于 RPM&#xff08;管理软件包的格式和工具集合&…

软考学习--计算机组成原理与体系结构

计算机组成原理与体系结构 数据的表示 进制转换 R 进制转换为 10 进制–按权展开法 10进制转换为2进制 原码 反码 补码 移码 原码 &#xff1a;数字的二进制表示反码 &#xff1a; 正数的反码等于原码&#xff0c;负数的反码等于原码取反补码&#xff1a; 正数的补码等…

跟着pink老师前端入门教程-day24

四、移动端WEB开发之响应式布局 1、响应式开发 1.1 响应式开发原理 就是使用媒体查询针对不同宽度的设备进行布局和样式的设置&#xff0c;从而适配不同设备的目的。 1.2 响应式布局容器 响应式需要一个父级做为布局容器&#xff0c;来配合子级元素来实现变化效果。 原理…

世界顶级名校计算机专业,都在用哪些书当教材?(文末送书)

目录 01《深入理解计算机系统》02《算法导论》03《计算机程序的构造和解释》04《数据库系统概念》05《计算机组成与设计&#xff1a;硬件/软件接口》06《离散数学及其应用》07《组合数学》08《斯坦福算法博弈论二十讲》参与规则 清华、北大、MIT、CMU、斯坦福的学霸们在新学期里…

FL Studio 21.2.3.4004 All Plugins Edition Win/Mac音乐软件

FL Studio 21.2.3.4004 All Plugins Edition 是一款功能强大的音乐制作软件&#xff0c;提供了丰富的音频处理工具和插件&#xff0c;适用于专业音乐制作人和爱好者。该软件具有直观的用户界面&#xff0c;支持多轨道录音、混音和编辑&#xff0c;以及各种音频效果和虚拟乐器。…

《统计学简易速速上手小册》第6章:多变量数据分析(2024 最新版)

文章目录 6.1 主成分分析&#xff08;PCA&#xff09;6.1.1 基础知识6.1.2 主要案例&#xff1a;客户细分6.1.3 拓展案例 1&#xff1a;面部识别6.1.4 拓展案例 2&#xff1a;基因数据分析 6.2 聚类分析6.2.1 基础知识6.2.2 主要案例&#xff1a;市场细分6.2.3 拓展案例 1&…

探索设计模式的魅力:迭代器模式让你轻松驾驭复杂数据集合

​&#x1f308; 个人主页&#xff1a;danci_ &#x1f525; 系列专栏&#xff1a;《设计模式》 &#x1f4aa;&#x1f3fb; 制定明确可量化的目标&#xff0c;并且坚持默默的做事。 文章目录 一、&#x1f4a1; 引言二、原理与结构 &#x1f4da;&#x1f465; 迭代器模式的关…

【二十八】springboot整合logback实现日志管理

本章节是记录logback在springboot项目中的简单使用&#xff0c;本文将会演示如何通过logback将日志记录到日志文件或输出到控制台等管理操作。将会从以下几个方面进行讲解。最后实现将特定级别的特定日志保存到日志文件。 一、依赖 <dependency><groupId>ch.qos.l…

基于python的遥感影像灰色关联矩阵纹理特征计算

遥感影像纹理特征是描述影像中像素间空间关系的统计特征&#xff0c;常用于地物分类、目标识别和变化检测等遥感应用中。常见的纹理特征计算方式包括灰度共生矩阵&#xff08;GLCM&#xff09;、灰度差异矩阵&#xff08;GLDM&#xff09;、灰度不均匀性矩阵&#xff08;GLRLM&…

51_蓝桥杯_led流水灯

一 原理图分析 二 三八译码器工作原理 三八译码器&#xff1a;3个输入控制8路互斥的低电平有效输出。 C B A 输出 0 0 0 Y0 0 0 1 Y1 0 1 0 Y2 0 1 1 Y3 1 0 0 Y4 1 0 1 Y5 1 1 0 Y6 1 1 1 Y7 三 锁存器工作原理 锁存器&#xff1a;当使…

OpenAI 全新发布文生视频模型 Sora,支持 60s 超长长度,有哪些突破?将带来哪些影响?

Sora大模型简介 OpenAI 的官方解释了在视频数据基础上进行大规模训练生成模型的方法。 我们下面会摘取其中的关键部分罗列让大家快速get重点。 喜欢钻研的伙伴可以到官网查看技术报告&#xff1a; https://openai.com/research/video-generation-models-as-world-simulator…

BDD - Python Behave 用户自定义配置文件

BDD - Python Behave 用户自定义配置文件 引言默认 behave.ini 配置文件自定义配置文件json 格式的配置文件ini 格式的配置文件 实例应用项目结构代码BDD/Features/user_data.feature 文件BDD/steps/user_data_steps.py 文件BDD/environment.py 文件默认配置文件 behave.ini自定…

BUGKU-WEB 留言板1

题目描述 题目截图如下&#xff1a; 进入场景看看&#xff1a; 解题思路 之间写过一题类似的&#xff0c;所以这题应该是有什么不同的那就按照之前的思路进行测试试试提示说&#xff1a;需要xss平台接收flag&#xff0c;这个和之前说的提示一样 相关工具 xss平台&#xf…

外包干了2个月,感觉技术明显退步...

先说情况&#xff0c;大专毕业&#xff0c;18年通过校招进入湖南某软件公司&#xff0c;干了接近4年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试&#xf…

BUGKU-WEB 头等舱

题目描述 题目截图如下&#xff1a; 进入场景看看&#xff1a; 解题思路 先看看源码再看看F12请求和响应 相关工具 略 解题步骤 查看源码&#xff0c;好家伙真的什么也没有 2. 看看F12请求和响应&#xff0c;找到了 得到Flag flag{a49c7aba1014c3673ec9982946d0545a…

鸿蒙新手入门-环境准备问题解析

Node.js版本与API配套关系 由于SDK的部分工具依赖Node.js运行时&#xff0c;推荐使用配套API版本的Node.js&#xff0c;保证工程的兼容性。 匹配关系见下表&#xff1a; API LevelNode.js支持范围API Level≤914.x&#xff08;≥14.19.1&#xff09;、16.xAPI Level>914.…

移动端App自动化之触屏操作自动化

工作中我们经常需要对应用的页面进行手势操作&#xff0c;比如滑动、长按、拖动等&#xff0c;AppiumDriver 为我们提供一个模拟手势操作的辅助类 TouchAction&#xff0c;可以通过它对手机屏幕进行手势操作。 具体用法参见链接&#xff1a;chromedriver下载地址与webview自动…

【开源】JAVA+Vue.js实现农村物流配送系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 系统登录、注册界面2.2 系统功能2.2.1 快递信息管理&#xff1a;2.2.2 位置信息管理&#xff1a;2.2.3 配送人员分配&#xff1a;2.2.4 路线规划&#xff1a;2.2.5 个人中心&#xff1a;2.2.6 退换快递处理&#xff1a;…