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

简介: 【算法解题思想】动态规划+深度优先搜索(C/C++)

动态规划

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

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

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

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

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

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

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

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

  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

3 2


输出 #1

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,具体解释注释在代码上。


代码实现:

#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

:图片来自罗老师讲解。

相关文章
|
1天前
|
算法 测试技术 定位技术
数据结构与算法——DFS(深度优先搜索)
数据结构与算法——DFS(深度优先搜索)
|
1天前
|
存储 算法 决策智能
【算法】博弈论(C/C++)
【算法】博弈论(C/C++)
|
1天前
|
存储 算法 C++
【算法】哈希映射(C/C++)
【算法】哈希映射(C/C++)
|
1天前
|
机器学习/深度学习 人工智能 算法
【算法】最长公共子序列(C/C++)
【算法】最长公共子序列(C/C++)
|
1天前
|
人工智能 算法 BI
一篇带你速通差分算法(C/C++)
一篇带你速通差分算法(C/C++)
|
1天前
|
人工智能 算法 C++
一篇带你速通前缀和算法(C/C++)
一篇带你速通前缀和算法(C/C++)
|
1天前
|
存储 算法 C++
弗洛伊德(Floyd)算法(C/C++)
弗洛伊德(Floyd)算法(C/C++)
|
1天前
|
存储 算法 程序员
迪杰斯特拉(Dijkstra)算法(C/C++)
迪杰斯特拉(Dijkstra)算法(C/C++)
|
1天前
|
算法 C++
【算法】DP背包问题(C/C++)
【算法】DP背包问题(C/C++)
|
1天前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题(C/C++)
【动态规划算法】蓝桥杯填充问题(C/C++)