DP之背包基础


目录

DP简介

01背包问题

采药(01背包例题)

完全背包

疯狂的采药(完全背包例题)

背包变式

装箱问题

砝码称重

质数拆分 

优化思考 


DP简介

全称Dynamic Programming即动态规划 

DP算法是解决多阶段决策过程最优化问题的一种常用方法。

多阶段决策过程是指这样一类特殊的活动过程,过程可以按时间顺序分解成若干个相互联系的阶段,在每一个阶段都需要做出决策,全部过程的决策是一个决策序列。

动态规划算法是解决多阶段决策过程最优化问题的一种常用方法,难度比较大,技巧性也很强。利用动态规划算法,可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。

有时遇到暴搜宽搜TLE、贪心分治不理想的情况时,用动态规划常常能够起到出人意料的效果

01背包问题

01背包问题最经典的问题就是给一个背包,让你从中选取n个物品且每个物品只能选一次,求取在背包容量满足大于等于背包内物品总体积的情况下,所能装的物品的最大价值或者最小价值,在对于这种问题时,我们常常利用数学集合的思想来解决

我们将背包当中的物品体积开一个v[N]数组,价值开一个w[N]数组,最后开一个dp二维数组

v[N]一维数组来存储每个物品的体积,w[N]一维数组来存储每个物品的价值

dp[i][j]表示从i个物品当中选取,且体积不超过j的选法,因当第一种情况成立时,返回值为0,第二种情况成立时,选取物品放入,返回的是所选取物品的价值,所以dp二维数组的返回值是此种选法情况的背包中物品的最大价值

对应每个dp[i][j]可以分为两种选择情况:

第一种选择情况为从i - 1个物品当中选取,且总体积不超过j的情况

第二种选择情况为从i个物品当中选取,且总体积不超过j的情况

在对于dp二维数组的模拟过程之中我们发现第二种情况要用i来描述,第一种情况要用i - 1描述,二者不完全一致,因此为了优化,我们将第二种情况进行合理变式为从i - 1个物品当中选取,且总体积不超过j - v[i]的情况

因此dp二维数组在依次枚举的时候就可以这样做变动

f[i][j] = f[i - 1][j];//第一种情况
if(j >= v[i])f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i] + w[i]);//第二种情况

两种情况求取最大值,第二种情况的成立条件是第i件物品的体积小于背包体积

采药(01背包例题)

辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”如果你是辰辰,你能完成这个任务吗?

题目描述

第一行有 2 个整数 T和M,用一个空格隔开,T 代表总共能够用来采药的时间,M 代表山洞里的草药的数目
接下来的 M行每行包括两个在1到 100之间(包括 1 和 100)的整数分别表示草药的时间和这株草药的价值。

输入

输出在规定的时间内可以采到的草药的最大总价值。

输出

输出在规定的时间内可以采到的草药的最大总价值

样例输入

70 3
71 100
69 1
1 2

样例输出

3

源代码

这道题目就是很经典的01背包问题,换汤不换药而已。背包中的物品换做了草药,背包的体积换作了最多能够使用的时间,物品的体积换做了采取草药的时间

#include <iostream>
using namespace std;
const int N = 3000+10;
int v[N];//存每株草药采取所花时间 
int w[N];//存每株草药的价值 
int T,M;
int dp[N][N];//存不同情况的不同最大价值 
int main()
{cin >> T >> M;for(int i = 1;i <= M;i ++ )cin >> v[i] >> w[i];for(int i = 1;i <= M;i ++ ){for(int j = 0;j <= T;j ++ ){dp[i][j] = dp[i - 1][j];if(j >= v[i])dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i]);}}cout << dp[M][T];return 0;
}

优化后源代码 

#include <iostream>
using namespace std;
const int N = 3000+10;
int v[N];//存每株草药采取所花时间 
int w[N];//存每株草药的价值 
int T,M;
int dp[N];//存不同情况的不同最大价值 
int main()
{cin >> T >> M;for(int i = 1;i <= M;i ++ )cin >> v[i] >> w[i];for(int i = 1;i <= M;i ++ ){for(int j = T;j >= v[i];j -- ){dp[j] = max(dp[j],dp[j - v[i]] + w[i]);}}cout << dp[T];return 0;
}

完全背包

简单来说,就是01背包的变形,其本质与01背包相似,只是在完全背包当中,每一个物品可以被选择无数次,而不是只能够选择一次,一般来说,完全背包问题是要进行性优化的,否则会TLE 

疯狂的采药(完全背包例题)

题目描述

LiYuxiang 是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同种类的草药,采每一种都需要一些时间,每一种也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”


如果你是 LiYuxiang,你能完成这个任务吗?

此题和原题(采药)的不同点:

1. 每种草药可以无限制地疯狂采摘。

2. 药的种类眼花缭乱,采药时间好长好长啊!师傅等得菊花都谢了!

输入

输入第一行有两个整数,分别代表总共能够用来采药的时间 t 和代表山洞里的草药的数目 m。

第2到第 (m+1) 行,每行两个整数,第 (i+1) 行的整数 ai, bi分别表示采摘第 i 种草药的时间和该草药的价值。

输出

输出一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值

样例输入

70 3
71 100
69 1
1 2

样例输出

140

源代码(已优化)

#include <iostream>
using namespace std;
const int N = 1000000+10;
int v[N];//存每株草药采取所花时间 
int w[N];//存每株草药的价值 
int T,M;
int dp[N];//存不同情况的不同最大价值 
int main()
{cin >> T >> M;for(int i = 1;i <= M;i ++ )cin >> v[i] >> w[i];for(int i = 1;i <= M;i ++ ){for(int j = v[i];j <= T;j ++ ){dp[j] = max(dp[j],dp[j - v[i]] + w[i]);}}cout << dp[T];return 0;
}

背包变式

装箱问题

题目描述

有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0<n≤30,每个物品有一个体积(正整数)。要求n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。

输入

1个整数,表示箱子容量
1个整数,表示有m个物品
接下来n行,分别表示这n个物品的各自体积

输出

1个整数,表示箱子剩余空间。

样例输入

24
6
8
3
12
7
9
7

样例输出

0

源代码

典型的完全背包问题,只不过求取最大值换做了求取最小值,简单变式即可 

#include <iostream>
using namespace std;
const int N = 1000000+10;
int v[N];//存物品的体积 
int V,M;
int dp[N];//存不同情况的不同最大占用空间
int main()
{cin >> V >> M;for(int i = 1;i <= M;i ++ )cin >> v[i];for(int i = 1;i <= M;i ++ ){for(int j = v[i];j <= V;j ++ ){dp[j] = max(dp[j],dp[j - v[i]] + v[i]);}}cout << V - dp[V];return 0;
}

砝码称重

题目描述

你有一架天平和 N 个砝码,这 N 个砝码重量依次是 W1, W2, · · · , WN。
请你计算一共可以称出多少种不同的重量?
注意砝码可以放在天平两边。

输入

输入的第一行包含一个整数 N。
第二行包含 N 个整数:W1, W2, W3, · · · , WN。
对于 50% 的评测用例,1 ≤ N ≤ 15。
对于所有评测用例,1 ≤ N ≤ 100,N 个砝码总重不超过 100000。

输出

输出一个整数代表答案。

样例输入

3
1 4 6

样例输出

10

源代码

[样例说明]
能称出的 10 种重量是:1、2、3、4、5、6、7、9、10、11。
1 = 1;
2 = 6 - 4(天平一边放 6,另一边放 4);
3 = 4 - 1;
4 = 4;
5 = 6 - 1;
6 = 6;
7 = 1 + 6;
9 = 4 + 6 - 1;
10 = 4 + 6;
11 = 1 +  4 + 6

此处的dp为状态01数组 

#include <iostream>
using namespace std;
const int N = 3000+10;
int f[N][N];
int w[N];
int n,sum = 0,ans = 0;
//sum为累加砝码的最大值,即最大边界值
//无论砝码如何放置,每个砝码只能使用一次且最小值一定大于等于1 
int main()
{cin >> n;for(int i = 1;i <= n;i ++ )//输入n个砝码的值 {cin >> w[i];sum += w[i];//累加最大边界值 }for(int i = 1;i <= n;i ++ )//外层循环砝码 {f[i][w[i]] = 1;//首先将该砝码重量标记为一种情况 for(int j = 1;j <= sum;j ++ )//内层循环砝码值 {if(f[i - 1][j] == 1)//若上层为1 {f[i][j] = 1;//则继承此种成立情况//对于新加的砝码值进行左右标记 f[i][j + w[i]] = 1; f[i][abs(j - w[i])] = 1;}}}for(int i = 1;i <= sum;i ++ )//扫描1~最大边界值的砝码值 {if(f[n][i] == 1)ans ++ ;//若为1则证明此砝码值可以整出来 }cout << ans;return 0;
}

质数拆分 

题目描述

2019可以被分解成若干个两两不同的素数,请问不同的分解方案有多少种?
注意:分解方案不考虑顺序,如 2 + 2017 = 2019 和 2017 + 2 = 2019 属于同一种方案。

输入

输出

55965365465060

样例输入

样例输出

55965365465060

源代码(已优化)

本题拉取素数优化的方法可以了解一下埃氏筛法与线性筛法

#include <iostream>
using namespace std;
const int N = 3000+10;
int prime[N];
bool isprime[N];
int idx = 0;
long long dp[N];
void init()//线性筛法拉取素数表 
{for(int i = 2;i <= 2019;i ++ ){if(!isprime[i]){prime[ ++ idx ] = i;}for(int j = 1;j <= idx && i <= 2019 / prime[j];j ++ ){isprime[i * prime[j]] = 1;if(i % prime[j] == 0)break;}}
}
int main()
{init();dp[0] = 1;//注意 for(int i = 1;i <= idx;i ++ ){for(int j = 2019;j >= prime[i];j -- ){dp[j] = dp[j] + dp[j - prime[i]];}}cout << dp[2019];return 0;
}

优化思考 

二维数组的开辟范围当然是限制性很大的,所以利用dp二维数组并不能够用来表示当物品种类过大的情况,那么动态规划的算法也就有了鸡肋性,不过幸好,我们可以将一维数组优化为二维数组,优化的方式是将代码等价变形,并减少非必要的元素遍历

当我们将dp数组的首坐标删去之后,我们可以发现循环里面的

dp[i][j] = dp[i - 1][j];

变成了

dp[j] = dp[j];

因此首行代码可以省去

根据第二行代码的情况进行减少数据遍历的优化,当第二行的情况成立时,j应该大于等于v[i],也就是说在从0~v[i] - 1的情况都是无意义的遍历,因此的原本两种情况可以合并为一种情况

if(j >= v[i])dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i]);

换做

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

但是此时变形之后的一维数组相当于

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

然而我们想要的是

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

所以我们要对于第二重循环的j进行改变 

for(int i = 1;i <= M;i ++ )
{for(int j = 0;j <= T;j ++ ){dp[i][j] = dp[i - 1][j];if(j >= v[i])dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i]);}
}

调整之后为

for(int i = 1;i <= M;i ++ )
{for(int j = T;j >= v[i];j -- ){dp[j] = max(dp[j],dp[j - v[i]] + w[i]);}
}

谨记

第二重循环从大到小遍历之后的优化为01背包优化也就是

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

第二重循环从小到大的遍历为完全背包优化也就是

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

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

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

相关文章

GitLab 服务变更提醒:中国大陆、澳门和香港用户停止提供服务(GitLab 服务停止)

目录 前言 一. 变更详情 1. 停止服务区域 2. 邮件通知 3. 新的服务提供商 4. 关键日期 5. 行动建议 二. 迁移指南 三. 注意事项 四. 相关推荐 前言 近期&#xff0c;许多位于中国大陆、澳门和香港的 GitLab 用户收到了一封来自 GitLab 官方的重要通知。根据这封邮件…

使用Grafana中按钮插件实现收发HTTP请求

最近项目中需要监控分布式集群的各项指标信息&#xff0c;需要用到PrometheusGrafana的技术栈实现对分布式集群的各个节点状态进行可视化显示&#xff0c;但是要求前端需要提供一个易用的接口让用户可以触发一些操作&#xff0c;例如负载高时进行负载均衡或弹性伸缩。网上找到的…

【前端】MVC模式详解:如何构建高效的Web应用程序?

&#x1f4a5; 欢迎来到[爱学习的小羊]的博客&#xff01;希望你能在这里发现有趣的内容和丰富的知识。同时&#xff0c;期待你分享自己的观点和见解&#xff0c;让我们一起开启精彩的交流旅程&#xff01;&#x1f31f;> 首页&#xff1a;爱学习的小羊 – 热爱AI、热爱Pyt…

对一篇单细胞RNA综述的评述:细胞和基因质控参数的选择

原文链接&#xff1a; https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6072887 摘要 单细胞RNA测序技术的发展加深了我们对于细胞作为功能单元的理解&#xff0c;不仅能基于成百到成千上万个单细胞的基因表达谱得到新的结论&#xff0c;还能发现新的具有特异基因表达谱的细胞…

【再谈设计模式】享元模式~对象共享的优化妙手

一、引言 在软件开发过程中&#xff0c;我们常常面临着创建大量细粒度对象的情况&#xff0c;这可能会导致内存占用过高、性能下降等问题。享元模式&#xff08;Flyweight Pattern&#xff09;就像是一位空间管理大师&#xff0c;它能够在不影响功能的前提下&#xff0c;有效地…

windos挂载目录到linux

验证环境麒麟V10 1: 在windows任意目录设置共享文件夹 2&#xff1a;记住网络路径\LAPTOP-86JV6NT1\gantie13_sdk 在linux中替换为本机ip级相对路径 比如本级ip是192.168.23.23&#xff0c;linux环境需要ping通本地地址 3&#xff1a; sudo apt-get install cifs-utils sud…

基于STM32单片机矿井矿工作业安全监测设计

基于STM32单片机矿井矿工作业安全监测设计 目录 项目开发背景设计实现的功能项目硬件模块组成设计思路系统功能总结使用的模块技术详情介绍总结 1. 项目开发背景 随着矿井矿工作业环境的复杂性和危险性逐渐增加&#xff0c;矿井作业安全问题引起了社会各界的广泛关注。传统的…

WebRTC服务质量(11)- Pacer机制(03) IntervalBudget

WebRTC服务质量&#xff08;01&#xff09;- Qos概述 WebRTC服务质量&#xff08;02&#xff09;- RTP协议 WebRTC服务质量&#xff08;03&#xff09;- RTCP协议 WebRTC服务质量&#xff08;04&#xff09;- 重传机制&#xff08;01) RTX NACK概述 WebRTC服务质量&#xff08;…

Java爬虫技术:按关键字搜索VIP商品详情

在数字化时代&#xff0c;电子商务平台的竞争日益激烈&#xff0c;而精准的数据采集和分析成为了企业获取竞争优势的关键。对于电商平台而言&#xff0c;能够根据用户输入的关键字快速搜索并展示VIP商品的详细信息&#xff0c;不仅能够提升用户体验&#xff0c;还能够增加销售机…

若依框架中的上传图片后如何实现回显到页面的

在日常开发中&#xff0c;总会遇到上传文件、图片等功能&#xff0c;然后本地开发的话&#xff0c;又没有像OSS、七牛等网络存储&#xff0c;这个时候通常将文件上传到本地&#xff0c;那么上传之后拿到的是本地的路径&#xff0c;存储到数据库中&#xff0c;查询的时候如何将本…

一键图片转3D模型,AI建模,一键把图片转三维模型,二维图片转3维模型,AI建模

一键图片转3D模型&#xff0c;AI建模&#xff0c;一键把图片转三维模型&#xff0c;二维图片转3维模型,AI建模&#xff0c;公测版&#xff0c;每天不定时免费开放&#xff0c;非常强大 1咱们先打开ai.glbxz.com http://ai.glbxz.com 22 2导入图片。支持单张和多张图片生成 3…

梳理你的思路(从OOP到架构设计)_设计模式Android + Composite模式

目录 1、Android Composite模式 2、范例之一 3、范例之二 1、Android Composite模式 在Android平台里&#xff0c;像Button或ImageButton等屏幕控件皆通称为View。多个View能组合在一起&#xff0c;就会各种排列方式&#xff0c;即称为「布局」 (Layout)。这Layout类别就是…

LabVIEW软件项目设计方案如何制定

制定LabVIEW软件项目设计方案需要综合考虑需求分析、架构设计、功能模块划分和时间预算等多个方面&#xff0c;确保项目开发过程高效、可控且最终满足目标要求。以下是一个详细的制定流程&#xff1a; ​ 1. 需求分析 目标定义&#xff1a;明确项目的目标&#xff0c;例如数据采…

机器学习(二)-简单线性回归

文章目录 1. 简单线性回归理论2. python通过简单线性回归预测房价2.1 预测数据2.2导入标准库2.3 导入数据2.4 划分数据集2.5 导入线性回归模块2.6 对测试集进行预测2.7 计算均方误差 J2.8 计算参数 w0、w12.9 可视化训练集拟合结果2.10 可视化测试集拟合结果2.11 保存模型2.12 …

Linux运维常见命令

vi/vim快捷键使用 1)拷贝当前行 yy ,拷贝当前行向下的5行 5yy&#xff0c;并粘贴&#xff08;输入p&#xff09;。 2)删除当前行 dd ,删除当前行向下的5行5dd 3)在文件中查找某个单词 [命令行下 /关键字&#xff0c;回车查找 ,输入n就是查找下一个 ] 4)设置文件的行号&…

MacOS下TestHubo安装配置指南

TestHubo是一款开源免费的测试管理工具&#xff0c; 下面介绍MacOS私有部署的安装与配置。TestHubo 私有部署版本更适合有严格数据安全要求的企业&#xff0c;支持在本地或专属服务器上运行&#xff0c;以实现对数据和系统的完全控制。 1、Mac 服务端安装 Mac安装包下载地址&a…

jumpserver docker安装

#安装jumpserver最新版本&#xff08;当前最新版本v4.5.0-ce&#xff09; curl -sSL https://resource.fit2cloud.com/jumpserver/jumpserver/releases/latest/download/quick_start.sh | bash#登录 http://192.168.31.168/ 默认账号密码 admin/ChangeMe 修改后&#xff1a; ad…

VBA技术资料MF243:利用第三方软件复制PDF数据到EXCEL

我给VBA的定义&#xff1a;VBA是个人小型自动化处理的有效工具。利用好了&#xff0c;可以大大提高自己的工作效率&#xff0c;而且可以提高数据的准确度。“VBA语言専攻”提供的教程一共九套&#xff0c;分为初级、中级、高级三大部分&#xff0c;教程是对VBA的系统讲解&#…

LabVIEW生物医学信号虚拟实验平台

介绍了一款基于LabVIEW的多功能生物医学信号处理实验平台的设计和实现。平台通过实践活动加强学生对理论的理解和应用能力&#xff0c;特别是在心电图(ECG)和脑电图(EEG)的信号处理方面。实验平台包括信号的滤波、特征提取和频谱分析等功能&#xff0c;能直观体验和掌握生物医学…

json字符串或者json文件转换成相应的bean,报错“Unrecognized field xxx , not marked as ignorable”

1. 异常描述 将一个json字符串或者json文件转换成相应的bean的时候&#xff0c;报如下错误&#xff1a; 2. 异常分析 bean中某个字段的get和set方法可能不是工具自动生成的&#xff0c;而是自己写的&#xff0c;譬如字段是“sInfo”&#xff0c;本来get方法是应该写成getsI…