第四十五章 动态规划——背包问题模型（二）
创始人
2024-05-16 18:07:20
0次

一、概述

我们在上一章中已经对背包模型做了一定地讲解，但是我们发现其实在上一章节中我们所介绍的例题大部分是给背包问题套上一个背景，当我们识破了背后的模型后，我们就可以直接套用模板，基本不需要对代码做改变。

那么在这一章节中，我们将讲解一些在背包问题代码上做出一定改变的题目。比如求方案数，方案等等。

二、例题

1、AcWing 1020. 潜水员

（1）问题

在这里插入图片描述

（2）分析

这道题表面上是一个二维费用背包模型，但是在模型题目中，我们的状态f[i][j][k]表示的是体积至多是j，重量至多是k，也就是一个小于等于的大小关系。

但是这道题不一样，我们要保证氧气和氮气足量，也就说可以多不能少，那么如果用二维费用背包模型表达的话，即状态f[i][j][k]表示的是体积至少是j，重量至少是k，反而是一个大于等于的大小关系。

由于状态含义的改变，我们的代码一定会改变，这里还涉及到了下标为负数时的处理。作者在之前的文章中做过详细地讲解，大家可以去看一看：AcWing 1020. 潜水员（二维费用背包的变形）详解

（3）代码

#include
#include
#include
using namespace std;
const int N=1010;
int n,m,k;
int o2[N],n2[N],w[N];
int f[N][30][80];
int main()
{cin>>m>>n>>k;for(int i=1;i<=k;i++)scanf("%d%d%d",o2+i,n2+i,w+i);memset(f,0x3f,sizeof f);f[0][0][0]=0;for(int i=1;i<=k;i++){for(int j=0;j<=m;j++){for(int p=0;p<=n;p++){f[i][j][p]=f[i-1][j][p];int m1=min(j,o2[i]),m2=min(p,n2[i]);f[i][j][p]=min(f[i-1][j-m1][p-m2]+w[i],f[i][j][p]);}}}cout<

2、AcWing 7. 混合背包问题

（1）问题

在这里插入图片描述

（2）分析

这道题则是各种背包问题的融合，只有大家掌握了各种单一的背包问题才能来解决这道题，但是如何将各种问题融合起来则是这道题的难点。也需要我们对代码模板做一定的改变和拼接。

详解请看：混合背包问题详解

（3）代码

#include
#include
#include
using namespace std;
const int N=2e4+10;
int f[N];
int n,m,v,w,s;
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){scanf("%d%d%d",&v,&w,&s);if(!s){for(int j=v;j<=m;j++)f[j]=max(f[j],f[j-v]+w);}else{if(s==-1)s=1;int k;for(k=1;k<=s;k*=2){for(int j=m;j>=k*v;j--){f[j]=max(f[j],f[j-k*v]+k*w);}s-=k;}if(s){for(int j=m;j>=s*v;j--){f[j]=max(f[j],f[j-s*v]+s*w);}}}}cout<

3、AcWing 12. 背包问题求具体方案

（1）问题

在这里插入图片描述

（2）分析

这道题也是求方案数，但是为了满足题目中最小字典序的条件，我们需要更改状态转移方程中的状态定义。这一点是比较难的。作者在之前的文章中做过介绍，不懂的同学可以去看一看：AcWing 12. 背包问题求具体方案

（3）代码

#include
#include
#include
using namespace std;
const int N=1010;
int v[N],w[N],f[N][N],cnt[N];
int n,m;
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)scanf("%d%d",v+i,w+i);for(int i=n;i>=1;i--){for(int j=0;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]);}}int j=m;int count=0;for(int i=1;i<=n;i++)if(j>=v[i]&&f[i+1][j-v[i]]+w[i]==f[i][j]){cout<

4、AcWing 11. 背包问题求方案数

（1）问题

在这里插入图片描述

（2）分析

这道题也是求方案，但是这次求的时方案数目，而这个过程也是一个DP，而这个DP的书写则需要用01背包的思路来写。所以这道题是利用背包问题的思想去解决新的问题，详解请看：
AcWing 11. 背包问题求方案数

（3）代码

#include
#include
#include
using namespace std;
const int N=1010,mod=1e9+7;
int f[N],g[N];
int main()
{int n,m;cin>>n>>m;for(int i=0;i<=m;i++)g[i]=1;for(int i=1;i<=n;i++){int v,w;cin>>v>>w;for(int j=m;j>=v;j--){if(f[j]g[j]=g[j-v];f[j]=f[j-v]+w;}else if(f[j]==f[j-v]+w)g[j]=(g[j]+g[j-v])%mod;}}cout<

5、AcWing 1013. 机器分配

（1）问题

在这里插入图片描述

（2）分析

这道题是分组背包的应用，以及在分组背包的条件下如何求方案的问题，详解请看：AcWing 1013. 机器分配（分组背包问题与方案记录）

（3）代码

#include
#include
#include
using namespace std;
const int N=15,M=20;
int f[N][M],v[N][M],w[N][M];
int way[N];
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&w[i][j]);v[i][j]=j;}for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){for(int k=0;k<=m;k++){if(j>=v[i][k])f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);}}}cout<=1;i--){for(int k=0;k<=m;k++){if(j>=v[i][k]&&f[i][j]==f[i-1][j-v[i][k]]+w[i][k]){way[i]=k;j-=k;break;}}}for(int i=1;i<=n;i++)cout<
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：谁你的财神 谁是你的穷神

下一篇：JavaEE day4 初识CSS

相关内容

热门资讯

安卓子系统windows11,... 你知道吗？最近科技圈可是炸开了锅，因为安卓子系统在Windows 11上的兼容性成了大家热议的话题。...
电脑里怎么下载安卓系统,电脑端... 你有没有想过，你的电脑里也能装上安卓系统呢？没错，就是那个让你手机不离手的安卓！今天，就让我来带你一...
索尼相机魔改安卓系统,魔改系统... 你知道吗？最近在摄影圈里掀起了一股热潮，那就是索尼相机魔改安卓系统。这可不是一般的改装，而是让这些专...
安卓系统哪家的最流畅,安卓系统... 你有没有想过，为什么你的手机有时候像蜗牛一样慢吞吞的，而别人的手机却能像风一样快？这背后，其实就是安...
安卓最新系统4.42,深度解析... 你有没有发现，你的安卓手机最近是不是有点儿不一样了？没错，就是那个一直在默默更新的安卓最新系统4.4...
android和安卓什么系统最... 你有没有想过，你的安卓手机到底是用的是什么系统呢？是不是有时候觉得手机卡顿，运行缓慢，其实跟这个系统...
平板装安卓xp系统好,探索复古... 你有没有想过，把安卓系统装到平板上，再配上XP系统，这会是怎样一番景象呢？想象一边享受着安卓的便捷，...
投影仪装安卓系统,开启智能投影... 你有没有想过，家里的老式投影仪也能焕发第二春呢？没错，就是那个曾经陪你熬夜看电影的“老伙计”，现在它...
安卓系统无线车载carplay... 你有没有想过，开车的时候也能享受到苹果设备的便利呢？没错，就是那个让你在日常生活中离不开的iOS系统...
谷歌安卓8系统包,系统包解析与... 你有没有发现，手机更新换代的速度简直就像坐上了火箭呢？这不，最近谷歌又发布了安卓8系统包，听说这个新...
微软平板下软件安卓系统,开启全... 你有没有想过，在微软平板上也能畅享安卓系统的乐趣呢？没错，这就是今天我要跟你分享的神奇故事。想象你手...
coloros是基于安卓系统吗... 你有没有想过，手机里的那个色彩斑斓的界面，背后其实有着一个有趣的故事呢？没错，我要说的就是Color...
安卓神盾系统应用市场,一站式智... 你有没有发现，手机里的安卓神盾系统应用市场最近可是火得一塌糊涂啊！这不，我就来给你好好扒一扒，看看这...
黑莓平板安卓系统升级,解锁无限... 亲爱的读者们，你是否还记得那个曾经风靡一时的黑莓手机？那个标志性的全键盘，那个独特的黑莓体验，如今它...
安卓文件系统采用华为,探索高效... 你知道吗？最近安卓系统在文件管理上可是有了大动作呢！华为这个科技巨头，竟然悄悄地给安卓文件系统来了个...
深度系统能用安卓app,探索智... 你知道吗？现在科技的发展真是让人惊叹不已！今天，我要给你揭秘一个超级酷炫的话题——深度系统能用安卓a...
安卓系统的分区类型,深度解析存... 你有没有发现，你的安卓手机里藏着不少秘密？没错，就是那些神秘的分区类型。今天，就让我带你一探究竟，揭...
安卓系统铠无法兑换,揭秘无法兑... 最近是不是有很多小伙伴在玩安卓系统的游戏，突然发现了一个让人头疼的问题——铠无法兑换！别急，今天就来...
汽车安卓系统崩溃怎么刷,一键刷... 亲爱的车主朋友们，你是否曾遇到过汽车安卓系统崩溃的尴尬时刻？手机系统崩溃还能重启，但汽车系统崩溃了，...
miui系统可以刷安卓p系统吗... 亲爱的手机控们，你是否对MIUI系统情有独钟，同时又对安卓P系统的新鲜功能垂涎欲滴？今天，就让我带你...