第四十五章 动态规划——背包问题模型（二）
创始人
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

相关内容

热门资讯

安卓系统苹果手机识别,跨界融合... 你知道吗？在科技飞速发展的今天，手机已经成为了我们生活中不可或缺的一部分。而说到手机，安卓系统和苹果...
harmonyos系统是不是安... 亲爱的读者，你是否曾好奇过HarmonyOS系统与安卓系统之间的关系？是不是安卓的“亲戚”？今天，就...
手机怎么装系统安卓,安卓系统安... 手机卡顿了？想给安卓系统来个大变身？别急，跟着我一步步来，保证让你的手机焕然一新！一、准备工作在开始...
安卓Linux系统内网穿透,A... 你有没有想过，你的安卓手机里那些看似普通的APP，其实可能正在悄悄地帮你打通网络世界的任督二脉呢？没...
win怎么安装安卓系统,Win... 亲爱的读者，你是不是对Win系统上的安卓应用垂涎已久，但又苦于不知道如何安装安卓系统呢？别急，今天我...
升级小米平板安卓系统,畅享全新... 你有没有发现，你的小米平板用久了，是不是感觉有点卡呢？别急，今天就来教你怎么给它来个系统升级，让它焕...
捷豹安卓系统车载,捷豹安卓系统... 哇，你有没有想过，当你的手机和汽车融为一体，会是怎样的体验呢？想象你正驾驶着你的捷豹，车窗外的风景如...
安卓1到10系统,安卓1.0至... 你有没有想过，手机里的安卓系统就像是我们生活中的好朋友，从青涩的少年成长为稳重的青年呢？从安卓1.0...
安卓8.0停用系统应用,提升使... 你知道吗？最近安卓系统又来了一次大动作，那就是安卓8.0系统开始停用一些系统应用了。这可真是让人有点...
安卓系统修改mtu值,轻松提升... 你有没有想过，你的安卓手机其实是个小小的电脑呢？它里面藏着许多可以自定义的秘密功能，就像修改MTU值...
安卓平板改window系统,探... 你有没有想过，你的安卓平板其实可以摇身一变，变成一个Windows系统的电脑呢？没错，就是那种可以运...
时空猎人安卓苹果系统,探索无尽... 你知道吗？最近在手机游戏圈里，有一款叫做《时空猎人》的游戏可是火得一塌糊涂呢！不管是安卓用户还是苹果...
安卓9.0系统的电视,新一代电... 亲爱的读者们，你是否也像我一样，对科技新玩意儿充满好奇？今天，我要和你聊聊一个让人眼前一亮的话题——...
小pc安装安卓系统,轻松安装安... 你有没有想过，你的小PC也能变身成为安卓系统的超级玩家呢？没错，就是那个平时默默无闻的小家伙，现在也...
高通备份安卓系统,全方位数据安... 你知道吗？在这个科技飞速发展的时代，手机备份可是个不得不提的话题。尤其是对于安卓用户来说，选择一个靠...
谷歌安卓系统有多少,从诞生到全... 你有没有想过，那个无处不在的谷歌安卓系统，究竟在全球有多少用户呢？它就像一个神秘的数字，每天都在悄悄...
fc黄金传说安卓系统,畅享复古... 你有没有听说最近安卓系统上的一款超酷的游戏——《FC黄金传说》？这款游戏可是让不少玩家都沉迷其中，今...
变小的我安卓系统,安卓系统演变... 你有没有发现，最近你的手机好像变轻了？没错，说的就是你，那个陪伴你多年的安卓系统。它悄无声息地进行了...
vivo安卓系统小彩蛋,体验科... 你知道吗？在vivo的安卓系统中，竟然隐藏着一些超有趣的小彩蛋！这些小彩蛋就像是在手机里埋下的宝藏，...
安卓系统如何强制重启,安卓系统... 手机突然卡壳了，是不是又该给它来个“大保健”了？没错，今天就来聊聊安卓系统如何强制重启。别小看这个看...