【C++算法模板】背包九讲(下):混合背包、二维费用背包、带依赖的背包、背包求方案数、背包求具体方案

2024-04-14 13:36

本文主要是介绍【C++算法模板】背包九讲(下):混合背包、二维费用背包、带依赖的背包、背包求方案数、背包求具体方案,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

    • 1)混合背包
    • 2)二维费用背包
    • 3)带依赖的背包
    • 4)背包求方案数
    • 5)背包求具体方案

1)混合背包

时间复杂度: O ( n 2 l o g 2 ) O(n^2log^2) O(n2log2),空间复杂度: O ( n ) O(n) O(n)

  • 关键点在于将多重背包二进制优化后变成 01 01 01背包和 01 01 01背包一起处理,完全背包单独处理,其实就是混合考了几种背包的处理方式
#include<bits/stdc++.h>
#define x first
#define y secondusing namespace std;typedef long long ll;
typedef pair<int,int> PII;// 解题思路: 三种物品三种放法,运用每组问题的解题思路即可const int N=1e3+5;int n,m;
int f[N];struct Thing {int kind; // 01?完全?多重?int v,w;
};
vector<Thing> things;int main() {cin>>n>>m;for(int i=0;i<n;i++) {int v,w,s;scanf("%d%d%d",&v,&w,&s);// 01背包问题if(s<0) things.push_back({-1,v,w});// 完全背包问题else if(s==0) things.push_back({0,v,w});// 多重背包问题else {for(int k=1;k<=s;k*=2) {s-=k;things.push_back({-1,v*k,w*k}); // 转换成01背包}if(s>0) things.push_back({-1,v*s,w*s});}}// 处理所有thingfor(auto item:things) {// 01背包/多重背包的处理→if(item.kind<0) {for(int j=m;j>=item.v;j--) {f[j]=max(f[j],f[j-item.v]+item.w);}}// 完全背包的处理→else {for(int j=item.v;j<=m;j++) {f[j]=max(f[j],f[j-item.v]+item.w);}}}cout<<f[m]<<endl;return 0;
}

2)二维费用背包

时间复杂度: O ( n 3 ) O(n^3) O(n3),空间复杂度: O ( n 2 ) O(n^2) O(n2)

  • 除了体积限制外加入了重量限制,处理方法和 01 01 01背包完全类似,只不过多了一重循环,和一维空间
#include<bits/stdc++.h>
#define x first
#define y secondusing namespace std;typedef long long ll;
typedef pair<int,int> PII;// 解题思路: const int N=1e3+5;
const int V=1e2+5; // 最大体积
const int M=1e2+5; // 最大载重
int n,v,m;
int f[V][M]; // 体积是i重量是j的最大价值int main() {cin>>n>>v>>m;for(int i=1;i<=n;i++) {// 边输入边处理int a,b,c;scanf("%d%d%d",&a,&b,&c);for(int j=v;j>=a;j--) {for(int k=m;k>=b;k--) {f[j][k]=max(f[j][k],f[j-a][k-b]+c);}}}cout<<f[v][m]<<endl;return 0;
}

3)带依赖的背包

时间复杂度: O ( n 3 ) O(n^3) O(n3),空间复杂度: O ( n ) O(n) O(n)

#include<bits/stdc++.h>
#define x first
#define y secondusing namespace std;typedef long long ll;
typedef pair<int,int> PII;// 解题思路: 选子物品前必须要选父物品const int N=1e2+5;
int n,m;
int h[N],e[N],ne[N],idx;
int v[N],w[N];
int f[N][N]; // f[i][j]:在选节点j的情况下总体积<=j,以i为根的子树的最大总收益是多少?// 每个子节点是一个物品组,每个组里面只能选一个,就变成了分组背包问题void add(int a,int b) {e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}void dfs(int u) {// 循环物品组for(int i=h[u];i!=-1;i=ne[i]) {int son=e[i]; dfs(son);// 枚举背包容量,因为一定要选择根节点// 所以j-v[u],01背包从大到小枚举for(int j=m-v[u];j>=0;j--) {// 枚举决策,这个组里面选哪个// 枚举这个子节点用哪个体积for(int k=0;k<=j;k++) {f[u][j]=max(f[u][j],f[u][j-k]+f[son][k]);}}}// 如果体积大于等于当前物品体积,把之前空出来的位置把物品价值加进去for(int i=m;i>=v[u];i--) f[u][i]=f[u][i-v[u]]+w[u];// 如果体积小于当前物品体积,整棵子树一个点都不能选for(int i=0;i<v[u];i++) f[u][i]=0;
}int main() {memset(h,-1,sizeof h);cin>>n>>m;int root;for(int i=1;i<=n;i++) {int p;scanf("%d%d%d",&v[i],&w[i],&p); // p表示依赖关系if(p==-1) root=i; // -1表示根节点else add(p,i);}dfs(root);cout<<f[root][m]<<endl; // 根节点为root背包最大容量为m的最大价值return 0;
}

4)背包求方案数

时间复杂度: O ( n 2 ) O(n^2) O(n2),空间复杂度: O ( n ) O(n) O(n)

  • 01 01 01 背包的基础上要求求出能得到最大价值的方案数共有多少种
  • 若初始化 f [ 1 ] f[1] f[1] f [ m ] f[m] f[m],那么 f [ j ] f[j] f[j] 代表的是背包容量不超过 j j j 时所得最大价值,为了便于统计,我们想让 f [ j ] f[j] f[j] 表示背包容量恰为 j j j 时的最大价值,所以需要把 f [ 1 ] f[1] f[1] f [ m ] f[m] f[m] 初始化为 − I N F -INF INF
  • 因为最优解不一定在 f [ m ] f[m] f[m] 空间不一定用完,所以还需要枚举出最大价值,再把最大价值对应的方案数累加起来,才是最终结果
#include<bits/stdc++.h>
#define x first
#define y secondusing namespace std;typedef long long ll;
typedef pair<int,int> PII;// 解题思路: 求最大价值的选法有多少种
// 为了便于统计,我们要让物理意义变为背包容量恰为j时的最大价值
// 所以要初始化为负无穷const int N=1e3+5;
const int mod=1e9+7; // 答案很大
const int INF=1e6;int n,m;
int f[N],g[N];int main() {cin>>n>>m;g[0]=1; // 初始化,背包容量为0时方案数是1// 背包容量为[1,m]时最大价值初始化为-INFfor(int i=1;i<=m;i++) {f[i]=-INF;}for(int i=0;i<n;i++) {int v,w;cin>>v>>w;for(int j=m;j>=v;j--) {// 选与不选的最大值int t=max(f[j],f[j-v]+w);int s=0;// 看哪种方案更优,把其方案数拿过来// 因为有可能f[j]=f[j-v]+w,即从两个状态转移过来都可以// 所以写两个并列的if,可以都加if(t==f[j]) s+=g[j];if(t==f[j-v]+w) s+=g[j-v];if(s>=mod) s-=mod; // 手动取模f[j]=t;g[j]=s;}}int maxw=0;// 求最优解,最优解不一定是m,因为物理意义变了for(int i=0;i<=m;i++) maxw=max(maxw,f[i]);int res=0;// 求总的方案数for(int i=0;i<=m;i++) {if(maxw==f[i]) {res+=g[i];if(res>=mod) res-=mod;}}cout<<res<<endl;return 0;
}

5)背包求具体方案

时间复杂度: O ( n 2 ) O(n^2) O(n2),空间复杂度: O ( n 2 ) O(n^2) O(n2)

#include<bits/stdc++.h>
#define x first
#define y secondusing namespace std;typedef long long ll;
typedef pair<int,int> PII;// 解题思路: 要求输出字典序最小的一种选法(123<31)按位比
// 看f[n][m]是从哪个状态转移过来的,若为f[n-1][m](没选),若为f[n-1][m-v[i]]+w[i](选了)
// 贪心求,如果能选第一个物品,那么必须选第一个物品,这样字典序是最小的,前面的物品能选则选
// 从后往前推,求方案从前往后推const int N=1e3+5;
int n,m;
int v[N],w[N],f[N][N]; // 前i个物品中背包容量不超过j的方案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 i=1,j=m; // 从后往前推,最大值是f[1][m]// 从前往后推最大值while(i<=n) {if(j>=v[i] && f[i+1][j-v[i]]+w[i]>=f[i+1][j]) {cout<<i<<' ';j-=v[i];i++;} else {i++;}}return 0;
}

这篇关于【C++算法模板】背包九讲(下):混合背包、二维费用背包、带依赖的背包、背包求方案数、背包求具体方案的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/903120

相关文章

利用Python打造一个Excel记账模板

《利用Python打造一个Excel记账模板》这篇文章主要为大家详细介绍了如何使用Python打造一个超实用的Excel记账模板,可以帮助大家高效管理财务,迈向财富自由之路,感兴趣的小伙伴快跟随小编一... 目录设置预算百分比超支标红预警记账模板功能介绍基础记账预算管理可视化分析摸鱼时间理财法碎片时间利用财

Maven中引入 springboot 相关依赖的方式(最新推荐)

《Maven中引入springboot相关依赖的方式(最新推荐)》:本文主要介绍Maven中引入springboot相关依赖的方式(最新推荐),本文给大家介绍的非常详细,对大家的学习或工作具有... 目录Maven中引入 springboot 相关依赖的方式1. 不使用版本管理(不推荐)2、使用版本管理(推

如何在 Spring Boot 中实现 FreeMarker 模板

《如何在SpringBoot中实现FreeMarker模板》FreeMarker是一种功能强大、轻量级的模板引擎,用于在Java应用中生成动态文本输出(如HTML、XML、邮件内容等),本文... 目录什么是 FreeMarker 模板?在 Spring Boot 中实现 FreeMarker 模板1. 环

Pandas透视表(Pivot Table)的具体使用

《Pandas透视表(PivotTable)的具体使用》透视表用于在数据分析和处理过程中进行数据重塑和汇总,本文就来介绍一下Pandas透视表(PivotTable)的具体使用,感兴趣的可以了解一下... 目录前言什么是透视表?使用步骤1. 引入必要的库2. 读取数据3. 创建透视表4. 查看透视表总结前言

Java Response返回值的最佳处理方案

《JavaResponse返回值的最佳处理方案》在开发Web应用程序时,我们经常需要通过HTTP请求从服务器获取响应数据,这些数据可以是JSON、XML、甚至是文件,本篇文章将详细解析Java中处理... 目录摘要概述核心问题:关键技术点:源码解析示例 1:使用HttpURLConnection获取Resp

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

Maven如何手动安装依赖到本地仓库

《Maven如何手动安装依赖到本地仓库》:本文主要介绍Maven如何手动安装依赖到本地仓库问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、下载依赖二、安装 JAR 文件到本地仓库三、验证安装四、在项目中使用该依赖1、注意事项2、额外提示总结一、下载依赖登

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息:读取"/proc/cpuinfo"文件获取磁盘信息:读取"/proc/diskstats"文

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注