动态规划之——背包DP(完结篇)

文章目录

  • 概要说明
  • 分组背包
    • 模板例题1
    • 思路
    • code
    • 模板例题2
    • 思路
    • code
  • 有依赖的背包问题
    • 模板例题
    • 思路
    • code
  • 背包问题求方案数
    • 模板例题
    • 思路
    • code
  • 背包问题求具体方案
    • 模板例题
    • 思路
    • code

概要说明

本文讲分组背包、有依赖的背包、 背包问题求方案数以及背包问题求具体方案
入门篇(01背包和完全背包问题):传送门
进阶篇(多重、混合、二维费用背包):传送门

分组背包

模板例题1

acwing-分组背包问题

思路

分组背包也是01背包的一个变形,01背包中我们有n个物品,在这题中我们有n个组别,每个组别有k个物品
因此我们可以对每个组别都进行01背包,在当前组别选出最优解的情况下在进行下一轮组别的01背包
它的状态转移方程和01背包一样,在01背包的基础上改动一点点即可
它的时间复杂度在 O ( n 3 ) O(n^3) O(n3)

code

const int N=1e3+5;
int cnt[N],f[N],w[N][N],v[N][N];
void solve(){int W,n,t=1;cin >> n >> W;for(int i=1;i<=n;++i){cin >> cnt[i];for(int j=1;j<=cnt[i];++j){cin >> w[i][j] >> v[i][j];}		 		}for(int i=1;i<=n;++i)   for(int j=W;j>=0;--j)for(int k=1;k<=cnt[i];++k){if(j>=w[i][k]){f[j]=max(f[j],f[j-w[i][k]]+v[i][k]);}}cout << f[W];return ;
}

模板例题2

通天之分组背包

思路

这题在模板例题1的基础上稍微变动了一点点,它没有给你确切的组数
因此我们需要先找出最大的组数,并另开一个数组存当前组数的下标
剩下的和模板例题1差不多,代码如下:

code

const int N=1e3+5;
int cnt[N],f[N],w[N],v[N],g[N][N];//g数组中,行存的是组别,列存的是个数,它的取值存的是下标
void solve(){int W,n,t=0;cin >> W >> n;for(int i=1;i<=n;++i){int x;cin >> w[i] >> v[i] >> x;cnt[x]++;t=max(t,x);g[x][cnt[x]]=i;}for(int i=1;i<=t;++i)   for(int j=W;j>=0;--j)for(int k=1;k<=cnt[i];++k){int st=g[i][k];//取出当前组别的下标if(j>=w[st]){f[j]=max(f[j],f[j-w[st]]+v[st]);}}cout << f[W];return ;
}

有依赖的背包问题

模板例题

有依赖的背包问题

思路

首先我们明确一点:想要取出子节点必须取出父节点
那么想要价值尽可能大,我们必须倒着遍历这颗树
遍历树最基本的算法是什么呢?
很显然,我们很快就能想到dfs回溯的思想,先来看这张图:
在这里插入图片描述

先看左边这条线1-2-4,我们将这颗树的节点分开来看,4的父节点为2,2的父节点1
那么我们想取出4的价值,首先必须取出2的价值,我们想取出2的价值,首先必须取出1的价值

我们倒着遍历树,当我们遍历到4时,发现4没有子节点,这时我们就回溯到前一个状态2
在回溯之前我们将4的价值存入到一个数组中,这时我们考虑状态2,它有2种选择,选或者不选
这时候它的状态转移方程和01背包是一样的

注意:在选状态4物品之前需要减去状态2的重量,因为状态2必须先选,才能选状态4

接着我们将选完的状态回溯到前一个状态1,同理,我们在选物品之前需要先减去状态1的重量
然后它也是有2种选择,选或者不选

对于其他线路也是同理,最终都会回溯到状态1,那么我们只需要从状态1开始进行dfs,遍历到树的叶节点时开始回溯即可

讲完思路,接着讲一下如何用代码实现出来
首先我们需要标记根节点的位置,用vector建树,将子节点存入父节点中
开一个二维数组,行代表节点,列代表重量w,所存的值为价值v

将根节点进行dfs,将当前 f [ x ] [ w − W ] 都标记为 v , x 代表节点, w 代表重量, W 为背包容量, v 为价值 f[x][w-W]都标记为v,x代表节点,w代表重量,W为背包容量,v为价值 f[x][wW]都标记为vx代表节点,w代表重量,W为背包容量,v为价值
这样方便我们递归回溯时进行状态转移
接着我们一直遍历当前节点的子节点,将子节点进行dfs循环,直到不能遍历为止
这样我们就像上面所说的,遍历到4不能遍历,回溯到2的状态
接着进行01背包的状态转移方程,当前循环结束,在回溯到上一次的状态
最终dfs循环结束,输出 f [ r o o t ] [ W ] f[root][W] f[root][W]

接下来我们看代码:

code

const int N=1e3+5;
int w[N],v[N],f[N][N];
vector<int> g[N];
int n,W;
void dfs(int x){for(int i=w[x];i<=W;++i) f[x][i]=v[x];//将w~W的重量都标记为vfor(auto y : g[x]){dfs(y);//一直循环子节点,直到不能循环为止for(int j=W;j>=w[x];--j)for(int k=0;k<=j-w[x];++k){//所选的物品必须减去当前重量f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]);//选子节点的物品还是不选子节点的物品}}
}
void solve(){cin >> n >> W;int root;for(int i=1;i<=n;++i){int x;cin >> w[i] >> v[i] >> x;if(x==-1) root=i;//标记else g[x].push_back(i);//建树}dfs(root);cout << f[root][W];return ;
}

背包问题求方案数

模板例题

背包问题求方案数

思路

这种类型的题目不需要我们求具体的价值,但是需要我们求最优价值的方案总数
那么我们首先还是需要算出最大的价值,然后将能到达当前价值的方案数进行相加

那么具体该如何实现呢?
我们需要在01背包的基础上,多开一个g数组,用于统计方案数
对于每步的状态来源,我们都有两种情况,一种是本身,一种是当前容量减去物品容量加上物品价值
这时我们新开一个变量temp,这个变量统计两种情况的最大值
若temp等于本身,那么 g [ i ] g[i] g[i]加上它本身
若temp等于当前容量减去物品容量加上物品价值,那么 g [ i ] + g [ j − w [ i ] g[i]+g[j-w[i] g[i]+g[jw[i]
每次加上都记得要取模
然后将当前状态 f [ j ] f[j] f[j]更新为temp
最后找出背包所能容量的最大价值,遍历f数组,若当前 f [ i ] f[i] f[i]等于最大价值,加上 g [ i ] g[i] g[i]

接下来看代码进一步理解

code

const int N=1e3+5;
int f[N],g[N],w[N],v[N];
void solve(){int n,W;cin >> n >> W;for(int i=1;i<=n;++i){cin >> w[i] >> v[i];}g[0]=1;//若不选物品,方案数为1for(int i=1;i<=n;++i)for(int j=W;j>=w[i];--j){int temp=max(f[j],f[j-w[i]]+v[i]);//temp为当前状态的最大值int c=0;//统计数量if(temp==f[j]) c=(c+g[j])%mod;//加上方案数if(temp==f[j-w[i]]+v[i]) c=(c+g[j-w[i]])%mod;f[j]=temp,g[j]=c;//状态转移}int maxn=0;for(int i=0;i<=W;++i) maxn=max(maxn,f[i]);//找到最大价值int ans=0;for(int i=0;i<=W;++i){if(f[i]==maxn) ans=(ans+g[i])%mod;//统计个数}cout << ans;return ;
}

背包问题求具体方案

模板例题

背包问题求具体方案

思路

首先我们需要回溯到原来的状态,这时候我们开一维数组就会丢失原来的状态,这时候必须开二维数组来存储数据
我们先考虑一个问题,我们是从前往后回溯,还是从后往前回溯呢?
答案很明显,我们需要从前往后回溯
为什么呢?
题目要求输出字典序最小的方案

我们拿一个例子来说明:
3 3
1 2
2 4
2 4

物品总数为3,背包容量为3,每个物品先输入重量,在输入价值
如果我们从后往前回溯,那么我们求出的具体方案为1 3(最后将数组颠倒一下)
可是答案很明显为1 2,这样字典序才是最小的

那么我们就将这种方法pass掉

那么我们一开始需要第n件物品的状态转移到第1件物品,这样 f [ 1 ] [ W ] f[1][W] f[1][W]就为最大的价值
首先还是先套01背包的模板,只不过从1开始变为从n开始
然后我们从序号1遍历到序号n,判断当前的状态是不是由当前价值加上上一个状态转移过来的,即 f [ i ] [ j ] = = f [ i + 1 ] [ j − w [ i ] ] + v [ i ] f[i][j]==f[i+1][j-w[i]]+v[i] f[i][j]==f[i+1][jw[i]]+v[i]
若满足,则当前背包容量减去 w [ i ] w[i] w[i],直接输出当前下标即可

接下来看代码

code

const int N=1e3+5;
int f[N][N],v[N],w[N],cnt[N];
void solve(){int n,W;cin >> n >> W;for(int i=1;i<=n;++i){cin >> w[i] >> v[i];}for(int i=n;i>=1;--i)//倒着来for(int j=0;j<=W;++j){f[i][j]=f[i+1][j];if(j>=w[i]) f[i][j]=max(f[i][j],f[i+1][j-w[i]]+v[i]);}for(int i=1,j=W;i<=n;++i){if(j>=w[i] && f[i][j]==f[i+1][j-w[i]]+v[i]){//判断状态cout << i << " ";j-=w[i];}}return ;
}

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

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

相关文章

STM32G070KBT6的RTC HAL库使用

*配置问题 首先使能时钟源&#xff0c;这里在时钟配置中选择LSI&#xff0c;为什么后面会说&#xff0c;然后使能Calender结构体&#xff0c;保证可以对RTC的年月日时分秒等进行写入和读取&#xff1b;alarmA和alarmB是闹钟&#xff0c;这里不用就Disable&#xff1b; Tam…

ShardingSphere之ShardingProxy集群部署

文章目录 介绍使用Zookeeper进行集群部署统一ShardingJDBC和ShardingProxy配置通过Zookeeper注册中心同步配置直接使用ShardingProxy提供的JDBC驱动读取配置文件 介绍 开发者手册 在conf/server.yaml配置文件中有下面这一段配置&#xff0c;就是关于集群部署的 mode: # typ…

极狐GitLab CICD Catalog Beta 功能介绍

极狐GitLab 是 GitLab 在中国的发行版&#xff0c;专门面向中国程序员和企业提供企业级一体化 DevOps 平台&#xff0c;用来帮助用户实现需求管理、源代码托管、CI/CD、安全合规&#xff0c;而且所有的操作都是在一个平台上进行&#xff0c;省事省心省钱。可以一键安装极狐GitL…

视觉SLAM中的数学基础01 -3D空间的位置表示

在视觉SLAM中&#xff0c;理解和表示3D空间中的位置是至关重要的。这涉及到多种数学概念和工具&#xff0c;如坐标系、向量、矩阵、旋转和平移等。这些数学基础构成了视觉SLAM算法的核心。以下是3D空间位置表示的基本数学概念。 这是一个表示世界坐标系和相机坐标系之间关系的3…

JNPF快速开发平台赋能数字办公方式转变

随着信息技术的飞速发展&#xff0c;数字化转型已成为各行各业提升效率、优化流程的重要手段。JNPF快速开发平台正是在这样的背景下应运而生&#xff0c;它通过简化开发流程&#xff0c;使得非技术人员也能参与到应用的构建中来&#xff0c;从而加速了数字办公方式的转变。 数字…

畅捷通基于Flink的实时数仓落地实践

摘要&#xff1a;本文整理自畅捷通总架构师、阿里云MVP专家郑芸老师在 Flink Forward Asia 2023 中闭门会上的分享。内容主要为以下四部分&#xff1a; 业务背景数仓建设具体案例未来展望 一、业务背景 畅捷通是用友旗下成员企业&#xff0c;一直持续专注于小微企业的数字化转…

4K YouTube to MP3 Pro:跨平台音频提取与转换的好用工具

4K YouTube to MP3 Pro是一款专为追求高品质音频体验的用户设计的跨平台&#xff08;支持Mac与Windows&#xff09;音频提取与转换软件。该软件以其卓越的音频提取能力和简便的操作流程&#xff0c;在同类产品中脱颖而出&#xff0c;成为众多用户的心头好。 功能强大&#xff…

AI革新3D建模:Stable Fast 3D工具的高效应用——图片快速生成3D模型

在3D建模领域,AI技术的介入正引发一场革命。Stable Diffusion(SD)的最新应用——Stable Fast 3D,为快速生成3D模型提供了一个强大的解决方案。以下是对这项技术及其应用的详细介绍和优化建议。 一、工具概览 Stable Fast 3D模型:这是一个基于AI的3D模型生成工具,可通过H…

社交电商系统:技术融合与商业创新

一、引言 随着社交平台的普及和电商系统的不断发展&#xff0c;社交电商系统作为一种新型的商业模式应运而生。这种模式结合了传统电子商务和社交媒体的优势&#xff0c;为消费者和商家提供了一个全新的购物和销售环境。本文将深入探讨社交电商系统的技术架构、主要模式、优势以…

每日学术速递8.8

1.Rethinking temporal self-similarity for repetitive action counting 标题&#xff1a;重新思考重复动作计数的时间自相似性 作者&#xff1a; Yanan Luo, Jinhui Yi, Yazan Abu Farha, Moritz Wolter, Juergen Gall 文章链接&#xff1a;https://arxiv.org/abs/2407.09…

LVS(Linux Virtual Server)详解

LVS&#xff08;Linux Virtual Server&#xff09;是一个用于负载均衡的开源软件项目&#xff0c;旨在通过集群技术实现高性能、高可用的服务器系统。它运行在Linux操作系统上&#xff0c;并且可以利用内核级的资源来提高性能和稳定性。 思维导图 LVS的工作原理 LVS主要基于Ne…

【树的遍历】

题目 代码 #include<bits/stdc.h> using namespace std;const int N 40;int in[N], pos[N]; //中序、后序 int idx[N]; //中序的值->索引 unordered_map<int, int> l, r; //根节点的左、右树根节点 int n; int build(int il, int ir, int pl, int pr) {int ro…

vite + tsc 打包报TS类型错误问题及解决方法

当新建vue3项目&#xff0c;package.json文件会自动添加一些配置选项&#xff0c; 这些选项基本没有问题&#xff0c;但是在实际操作过程中&#xff0c;列举一个目前我遇到的一个问题&#xff1a;打包后报了一堆TS类型错误&#xff0c;怎么消除这些错误&#xff1f; 报错信息&a…

ubuntu20从docker安装到制作自己的镜像使用记录

ubuntu20从docker安装到制作自己的镜像使用记录 第一章&#xff1a;配置环境 1.ubuntu20 2.docker镜像18.04 3.参考&#xff1a;https://www.runoob.com/docker/docker-tutorial.html 第二章&#xff1a;安装docker 一、安装docker 参考1&#xff1a;Ubuntu安装docker并运…

Go语言编程大全,web微服务数据库十大专题精讲

本课程主要从数据结构、Go Module 依赖管理、IO编程、数据库编程、消息队列、加密技术与网络安全、爬虫与反爬虫、web开发、微服务通用技术、Kitex框架等方面讲解~ 链接&#xff1a;https://pan.quark.cn/s/d65337a0e60d

视频循环存储的实现

目录 1. 三方工具 2. 视频存储的实现 2.1 分段存储 - 比如每15分钟 2.2 对齐到15分钟整边界 2.3 循环存储的实现 video_space_daemon.sh 3.封装 3.1 主执行程序&#xff0c;修订版 3.2 创建服务 3.3 service关联的执行脚本文件 4.额外的工作 附录A: ffmpeg视频存储…

矩阵算法的介绍和实现

一. 介绍 首先我们要清楚矩阵是什么&#xff1a;矩阵是一个按照长方阵列排列的复数或实数集合 1> 定义 定义&#xff1a;mn矩阵为mn个数排成的m行n列的表格&#xff0c;当mn时&#xff0c;矩阵A称为n阶方阵或者n阶矩阵。零矩阵&#xff1a;矩阵所有元素都为0。同型矩阵&a…

一个简单的录音软件(利用QT录音,ffmpeg进行音频重采样,fdk-aac编码)

录音软件是一种非常有用的工具&#xff0c;可以帮助我们记录和存储语音信息。在本文中&#xff0c;我们将介绍一个简单的录音软件&#xff0c;该软件利用QT进行录音&#xff0c;使用ffmpeg进行音频重采样&#xff0c;并使用fdk-aac编码。 一、 环境介绍 1、QT版本: QT5.…

SuccBI+低代码文档中心 — 可视化分析(仪表板)(上)

有关仪表板的设计器&#xff1a; 查询设置 由于仪表板的设计器是所见即所得的&#xff0c;可以将当前制作的内容和数据的查询结果实时展示在界面中&#xff0c;当引入到仪表板的模型数据量较大时&#xff0c;为了提高设计器界面的查询性能&#xff0c;提供了以下两种方法&…

Azure openai connection with javascript

题意&#xff1a;使用JavaScript与Azure OpenAI进行连接 问题背景&#xff1a; I have created my chatbot with javascript and used open ai. I need to change it to azure open ai but can not find the connection details for javascript. This is how i connect with p…