【算法解题思想】动态规划+深度优先搜索（C/C++）

2024-09-23 17:20:19 浏览数 (2)

动态规划：

动态规划（Dynamic Programming，简称 DP）是一种在数学、管理科学、计算机科学和经济学中用于求解决策过程最优化的数学方法。它通过将复杂问题分解成简单的子问题来解决，通过保存子问题的解，避免重复计算，从而提高效率。

动态规划通常适用于具有以下特点的问题：

  1. 最优子结构：动态规划每一步的最优，局部最优解。
  2. 重叠子问题：一个问题分解成多个子问题，这些问题会有重复的问题。
  3. 无后效性：一个状态的值被状态转移方程计算出来，那么它就是不可以变化的，后面的状态可以把他拿过来用。

动态规划的基本步骤包括：

  1. 定义状态：求解动态规划，先要定义dp数组，其意义是什么。
  2. 建立状态转移方程：根据问题的特点，以及联系性，对状态建立状态转移方程。
  3. 确定初始状态和边界条件：确定了状态转移方程，那么就要确定初始条件、值，保证状态转移方程的计算。
  4. 计算状态：按照状态转移方程计算每一个状态。
  5. 得到解：根据计算的状态，以及题目所问的是什么进行输出应该的答案。

动态规划的应用非常广泛，包括但不限于：

  • 最短路径问题：如Dijkstra 算法和 Floyd-Warshall 算法。
  • 背包问题：包括 0/1 背包问题和树形背包等等。
  • 最长公共子序列：求解两个序列的最长公共子序列。
  • 最大子矩阵：求解二维数组中最大的子矩阵的值。
wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==

动态规划的实现方法通常有两种：

  1. 自顶向下的递归方法：使用递归公式从一般到特殊解决问题，通常需要配合记忆化来避免重复计算，又称记忆化搜索。
  2. 自底向上的迭代方法：从最简单的子问题开始，逐步构建复杂问题的解。

深度优先搜索：

算法介绍：

深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。这种算法会尽可能深地搜索图的分支，直到找到目标节点或达到叶节点（没有子节点的节点），然后回溯到上一个分支继续搜索。DFS可以用于许多问题，比如路径寻找、连通性验证、拓扑排序等。

基本步骤：

DFS通常使用递归或栈来实现。以下是DFS的基本步骤：

选择起始点：选择图中的一个点作为起始点。 访问节点：标记起始节点为已访问，并将该节点加入递归或栈中。 探索邻接节点：从该点周围取出一个点，检查它的所有未访问的邻接节点。 递归或迭代：对每个未访问的邻接节点，将其标记为已访问，然后将其推入递归或栈中。 回溯：当当前节点的所有邻接节点都被访问后，递归中回溯/从栈中弹出该节点，继续搜索上一个点的其他分支。 结束条件：当栈为空或找到目标节点时，搜索结束。

题目描述

给定一个信封，最多只允许粘贴 N 张邮票，计算在给定 K（N K≤15）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值 MAX，使在 1 至 MAX 之间的每一个邮资值都能得到。

例如，N=3，K=2，如果面值分别为 1 分、4 分，则在 1∼6 分之间的每一个邮资值都能得到（当然还有 8 分、9 分和 12 分）；如果面值分别为 1 分、3 分，则在 1∼7 分之间的每一个邮资值都能得到。可以验证当 N=3，K=2 时，7 分就是可以得到的连续的邮资最大值，MAX=7，面值分别为 1 分、3 分。

输入格式

2 个整数，代表 N，K。

输出格式

输出共 2 行。

第一行输出若干个数字，表示选择的面值，从小到大排序。

第二行，输出 MAX=S， 表示最大的面值。

输入输出样例

输入 #1

代码语言：javascript复制
3 2

输出 #1

代码语言：javascript复制
1 3
MAX=7

解题思路：

此题主要利用了dp dfs,根据题目来看需要k种邮票，那么需要哪几种邮票，这就需要枚举，dfs去每一步搜索，题目中要求最大连续长度，考虑dp去解决，要求最大连续长度，意思就是通过这k种面值，能够连续不间断组成1~？之间的每一个数，那么我定义一个f[M]表示通过k种面值得到分值为M的最少邮票张数，只要这个值小于题目中给定的邮票张数n，那么从小到达遍历，此位置前面的都是连续的，当找到第一个不满足<n的分数i时，那么它前面i-1都是连续的，即此方案的最大连续长度为i-1，如果找不到这样的条件，那么能组成的值都是小于n的，最大连续长度就是最大的邮票值*n。

那么我们重新顺一下解题思路，首先枚举这k种邮票面值组合，我们解决办法是最简单的dfs，我们枚举出这k种面值组合，对它进行求解最大连续长度，处理办法是dp，具体解释注释在代码上。

代码实现：

代码语言：javascript复制
#include<iostream>
#include<cstring>
using namespace std;
const int N=20;
const int inf=0x3f3f3f;
int n,k,res;//res保存答案
int a[N],ans[N],f[50000];//f[i]拼面值为i所需要最小张数
//a[i]组成的分数中间过渡数组，ans[i]满足条件的答案分数数组
int dp(int t,int mx){
	f[0]=0;//初始化特例
	for(int i=1;i<=a[t]*n;i  )f[i]=inf;//初始化正无穷
	for(int i=1;i<=k;i  ){//k种位数
		for(int j=a[i];j<=a[t]*n;j  ){//最大连续长度至少以自己分数为起始，最大到填满n张最大的面值a[t]
			f[j]=min(f[j],f[j-a[i]] 1); //类似于背包更新
		}
	}
	for(int i=1;i<=a[t]*n;i  ){
		if(f[i]>n){//若此时填的面值张数大于邮票可以贴的最大张数，就说明此时i不满足，前i-1是满足的
			return i-1;
		}
	}
	return a[t]*n;//若前面都成立那么最大连续分数就是最大值分数*张数
} 
void dfs(int dep,int x){//dep种分数组成x为连续最大长度 
	if(dep==k 1){//当分数种数为k种，满足条件
		if(x>res){//此时最大连续长度大于res满足更新条件
			res=x;//更新
			for(int i=1;i<=k;i  ){
				ans[i]=a[i];
			}
		}
		return;
	}
	for(int i=a[dep-1] 1;i<=x 1;i  ){//为了不避免重复，至少是上一位的分数值 1,最大到x 1，否则前面的也会不连续
		a[dep]=i;
		int t=dp(dep,x);//t更新最大连续长度
		dfs(dep 1,t);
	}
}
int main(){
	cin>>n>>k;
	dfs(1,0);//从1开始去找，第一个分必是1，初始最大长度为0
	for(int i=1;i<=k;i  )
      cout<<ans[i]<<" ";
    cout<<endl;
    cout<<"MAX="<<res<<endl;
	return 0;
}

题后总结：

此题博主感觉难度较大，如果题量够大，可能对他们来说，一眼就出思路，dfs dp这种题第一次做，当时看的是罗老师的B站讲解，大家看不懂的可以去看看。

信奥编程罗老师：P1021 [NOIP1999 提高组] 邮票面值设计_哔哩哔哩_bilibili

注：图片来自罗老师讲解。

搜索 算法 c++ 递归 动态规划

0 人点赞