首页 > 其他分享 >【笔记】动态规划

【笔记】动态规划

时间:2024-11-03 14:59:16浏览次数:3  
标签:背包 int max 笔记 问题 物品 动态 规划 dp

前言

动态规划(Dynamic Programming)是c++算法学习当中十分重要而变化灵活的一部分分支,这种算法是通过递推的方式从而达到求出最优解的目的。

动态规划基本原理

能用动态规划解决的问题,需要满足三个条件:最优子结构,无后效性和子问题重叠。
  1. 最优子结构:每个子问题的解是其本身的最优解

  2. 无后效性:已经求解的子问题,不会再受到后续决策的影响。

  3. 动态规划中可能存在大量的子问题造成的答案重叠。

动态规划基本思路

  1. 将原问题划分为若干阶段,每个阶段对应若干个子问题,提取这些子问题的状态与特征

  2. 寻找每一个状态的可能 决策,或者说是各状态间的相互转移方式和关系。

  3. 按顺序求解每一个阶段的问题。

背包DP

0-1背包问题

[USACO07DEC]Charm Bracelet S - 洛谷

题目大意:

已知有 \(n\) 个物品,第 \(i\) 个物品的重量 \(w_{i}\),价值\(v_{i}\),背包的总容量 \(W\)。求背包可以容下的最大价值。

解题思路

该类型是典型的背包问题,可以设置一个二维数组 \(dp_{i,j}\),表示在只能放下前 \(i\) 个物品的情况下,容量为 \(j\) 的背包所能达到的最大价值。

考虑一下状态转移方程,当已经放完前面 \(i - 1\) 个物品的时候,对于第 \(i\) 个物品,有两种选择:

  • 不放入背包当中,此时 \(dp_{i, j} = dp_{i - 1, j}\)。

  • 放入背包当中,此时 \(dp_{i, j} = dp_{i - 1, j - w_{i}} + v_{i}\)。

根据动态规划最优子结构的特征,可以得到接下来的状态转移方程:

\[dp_{i,j} = \max(dp_{i - 1, j}, dp_{i - 1, j - w_{i}} + v_{i}) \]

然而在大多数的情况下,直接使用二维数组记录会导致MLE,而又由于该状态转移方程中的第一维只和前一次相关,所以我们可以将第一维压缩为 \(2\) 甚至是可以直接将方程变为一维的。如下:

\[dp_{i,j} = \max(dp_{i \oplus 1, j}, dp_{i \oplus 1, j - w_{i}} + v_{i}) \]

\[dp_{j} = \max(dp_{ j}, dp_{ j - w_{i}} + v_{i}) \]

大部分背包问题的转移方程都是在此基础上推导出来的。

代码实现

for (int i = 1; i <= n; i++)
    for (int j = W; j >= w[i]; j--)
        f[j] = max(f[j], f[j - w[i]] + v[i]);

完全背包问题

疯狂的采药 - 洛谷

解题思路

完全背包模型与 0-1 背包类似,与 0-1 背包的区别仅在于一个物品可以选取无限次,而非仅能选取一次。

我们可以仿照0-1背包进行定义动态规划数组: \(dp_{i,j}\),表示在只能放下前 \(i\) 个物品的情况下,容量为 \(j\) 的背包所能达到的最大价值。

朴素做法:对于第 i 件物品,枚举其选取了多少个物品来进行转移,转移方程如下:

\[dp_{i,j} = \max\limits_{k=0}\limits^{+\infty}(dp_{i-1,j},dp_{i - 1,j - k \times w_{i}} + v_{i} \times k) \]

根据优化之后,我们可以通过状态转移方程的重叠子问题优化了复杂度,其状态转移方程如下:

\[dp_{j} = \max(dp_{j}, dp_{j - w_{i}} + v_{i}) \]

代码实现

for (int i = 1; i <= n; i++)
    for (int j = w[i]; j <= W; j++)
        if (f[j - w[i]] + v[i] > f[j])
            f[j] = f[j - w[i]] + v[i];

多重背包

4. 多重背包问题 I - AcWing题库

解题思路

第一种方法:我们可以采取朴素暴力的思想,将只能选择 \(s\) 件物品转化为 \(s\) 件相同的物品,每种只能选一次的方法,这样我们就可以将其转化为简单的0-1背包问题了。

int main()
{
	// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int m, n; cin >> m >> n;
	for (int i = 1; i <= n; i++)
	{
		int s, v, w; cin >> s >> w >> v;
		while (s--)
			for (int j = m; j >= v; j--)
				dp[j] = max(dp[j], dp[j - v] + w);
	}
	cout << dp[m] << '\n';
	return 0;
}

但是这样子拆分不能解决数据较大时的情况,会使得时间复杂度和空间复杂度十分庞大。分析后可发现是由于将其拆分后存在多个相同的方案被重复计算,因此我们可以采用一种方式进行分组优化,使得每一种方案仅仅被计算了一次——二进制分组优化

第二种优化方法:将一种物品的最多数量 \(s\) 用二进制的方法进行拆分,即 \(s = 1 + 2 + 4 + 8 + \dots\),这种方法不仅可以减少空间的复杂度,由于遍历一次只需要 \(\log_{2} s\) 次,而

5. 多重背包问题 II - AcWing题库

代码实现

signed main()
{
	// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int m, n; cin >> m >> n;
	for (int i = 1; i <= n; i++)
	{
		int s, v, w; cin >> s >> w >> v;
		
		vector <int> vc;
		int x = 1; 
		while (s >= x)
			vc.push_back(x), s -= x, x <<= 1;
		if (s != 0) vc.push_back(s);
		// for (auto k : vc) cout << k << ' ';
		
		for (auto k : vc)
			for (int j = m; j >= k * v; j--)
				dp[j] = max(dp[j], dp[j - k * v] + k * w);
	}
	cout << dp[m] << '\n';
	return 0;
}

当然还有更有的方法。通过用 \(v_i\)​ 的同余系进行分类,我们不难发现,在对于枚举个数的时候,每个物品只会从它的同余系转移过来。由此通过同余系的划分保证了序列的单调性,使用单调队列进行线性的优化。与之不同的是,背包的大小以及价值会随着数量而变化,只需要加上偏移量即可。

6. 多重背包问题 III - AcWing题库

代码实现

cin >> n >> V;
	for (int i = 1; i <= n; i ++)
	{
		int v, w, s; cin >> v >> w >> s;
		memcpy(g, f, sizeof g);
		for (int j = 0; j < v; j ++)
		{
			int hh = 0, tt = -1;
			for (int k = j; k <= V; k += v)
			{
				if (hh <= tt && q[hh] < k - s * v) hh ++;
				if (hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w);
				
				while (hh <= tt && g[q[tt]] <= g[k] - (k - q[tt]) / v * w) tt --;
				q[++ tt] = k;
			}
		}
	}
	cout << f[V] << '\n';

数位 DP

定义

数位 DP 是一种将数据范围按照位数进行拆分,关注每一位上的数字的选择,从而降低时间复杂度,解决有如下特征的特定问题。

  1. 提供数字区间和特殊的限制,难以甚至无法使用数学推理方法得出答案。
  2. 数据范围极大,无法线性暴力枚举验证。
  3. 主要要求计数。

核心原理

本篇着重讲述 dfs 的 DP 做法。

将暴力枚举的方式写成了类似 dfs 的方式以方便使用记忆化搜索加快搜索效率。

数位 DP 之所以可以使用记忆化搜索,是因为由于从高位向低位枚举时往往有大量重复的低位部分重复处理。在这种大量重叠的情况下,记忆化搜索将起到很大的优化作用。

大致模板

预处理数位数组

int divide(int x)
{
	len = 0;
	while (x) num[++ len] = x % 10, x /= 10;
	return dfs...;
}

dfs 数组

int dfs(int pos, int info, bool limit, bool pre)
    // 传参的信息有:当前数位所处的位置,与题目有关的信息
    // 	是否存在限制(即当且的子问题是否处于问题的边界上)
    // 是否存在前导 0(视题目而定,可有可无)
{
	if (!pos) return info;	// 判断边界
    if (!limit && f[pos][info][pre] != -1)
        return f[pos][info][pre];	// 记忆化搜索
   	int res = 0;
    int up = limit ? num[pos] : 9;	// 依据边界限制上边界
    for (int i = 0; i <= up; i ++)
    {
		res += dfs(pos - 1, info..., limit && i == num[pos], pre && !i);
        	// 向下搜索并向上传递计数
        ...;
    }
    ...;
    if (!limit) f[pos][info][pre] = res;	// 更新记忆数组
    return res;
}

例题

P4999 烦人的数学作业

P2657 [SCOI2009] windy 数

P2602 [ZJOI2010] 数字计数

NFLSOJ 不降数

标签:背包,int,max,笔记,问题,物品,动态,规划,dp
From: https://www.cnblogs.com/ThySecret/p/18523436

相关文章

  • 【笔记/模板】A*算法
    A*算法定义A*搜索算法(\(\text{A*searchalgorithm}\))是一种在图形平面上,对于有多个节点的路径求出最低通过成本的算法。它属于图遍历(英文:\(\text{Graphtraversal}\))和最佳优先搜索算法(英文:\(\text{Best-firstsearch}\)),亦是BFS的优化,用到了启发式搜索的思维。启发式搜索(......
  • 【笔记/模板】Bellman-Ford
    Bellman-Ford求最短路和负环时间复杂度:\(O(nm)\)【模板/笔记】Johnson算法boolBellman_Ford(){memset(dist,0x3f,sizeofdist);for(intk=1;k<n;k++)for(intver=1;ver<=n;ver++)for(inti=h[ver];~i;i=ne[i])......
  • C++学习笔记
    一、从C转向C++1.1、使用const和inline而不#define使用constconstintm=10;intn=m;上述代码在C中,编译器会先到m的内存中取出数据,再赋值给n;但在C++中,会直接将10赋值给n。C++的常量更类似于#define,是一个替换过程。#define经常不被认为是语言的一部分。define本......
  • 「Mac畅玩鸿蒙与硬件22」鸿蒙UI组件篇12 - Canvas 组件的动态进阶应用
    在鸿蒙应用中,Canvas组件可以实现丰富的动态效果,适合用于动画和实时更新的场景。本篇将介绍如何在Canvas中实现动画循环、动态进度条、旋转和缩放动画,以及性能优化策略。关键词Canvas组件动态绘制动画效果动态进度条旋转和缩放性能优化一、使用定时器实现动......
  • 易语言模拟真人动态生成鼠标滑动路径
    一.简介鼠标轨迹算法是一种模拟人类鼠标操作的程序,它能够模拟出自然而真实的鼠标移动路径。鼠标轨迹算法的底层实现采用C/C++语言,原因在于C/C++提供了高性能的执行能力和直接访问操作系统底层资源的能力。鼠标轨迹算法具有以下优势:模拟人工轨迹:算法能够模拟出非贝塞尔曲线的......
  • Python模拟真人动态生成鼠标滑动路径
    一.简介鼠标轨迹算法是一种模拟人类鼠标操作的程序,它能够模拟出自然而真实的鼠标移动路径。鼠标轨迹算法的底层实现采用C/C++语言,原因在于C/C++提供了高性能的执行能力和直接访问操作系统底层资源的能力。鼠标轨迹算法具有以下优势:模拟人工轨迹:算法能够模拟出非贝塞尔曲线的......
  • 猿人学web端爬虫攻防大赛赛题第2题——动态cookie
    题目网址:https://match.yuanrenxue.cn/match/2解题步骤看触发的数据包。在请求头中的cookie字段中m变量的值一看就是加密过的。看Initiator模块中的request。点进去,打断点。我们只能在响应内容中看到页面数据,但是关于m的加密却是没有看到。刷新界面,出现如下画面......
  • C++模拟真人动态生成鼠标滑动路径
    一.简介鼠标轨迹算法是一种模拟人类鼠标操作的程序,它能够模拟出自然而真实的鼠标移动路径。鼠标轨迹算法的底层实现采用C/C++语言,原因在于C/C++提供了高性能的执行能力和直接访问操作系统底层资源的能力。鼠标轨迹算法具有以下优势:模拟人工轨迹:算法能够模拟出非贝塞尔曲线的......
  • git学习笔记--Linux
    理解什么是git,怎么用git,git的好处安装下载gitsudoapt-getinstallgit在终端输入git-v能出现版本信息就是下载成功了git的使用方式命令行在终端输入git命令git命令常用#初始化设置用户名和邮箱,这样才知道是谁修改的内容gitconfig--globaluser.name"yourname"......