当前位置:   article > 正文

数据结构与算法笔记-----动态规划简述(以Coin change为例图示+C语言实现)_coinchange控制流图

coinchange控制流图

什么是动态规划

动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。

动态规划的常见分类

编号动态规划:最大不下降子序列
划分动态规划:矩阵链乘、凸多边形三角剖分
数轴动态规划:0-1背包
前缀动态规划:最长公共子序列
树形动态规划:最优二分搜索树

或者

线性动规:拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等;
区域动规:石子合并, 加分二叉树,统计单词个数,炮兵布阵等;
树形动规:贪吃的九头龙,二分查找树,聚会的欢乐,数字三角形等;
背包问题:01背包问题,完全背包问题,分组背包问题,二维背包,装箱问题,挤牛奶等

或者

计数:如选出k个数使得和是sum
求最大最小值:最大上升子序列
求存在性:博弈

算法原理

基本思想:问题的最优解如果可以由子问题的最优解推导得到,则可以先求解子问题的最优解,在构造原问题的最优解;若子问题有较多的重复出现,则可以自底向上从最终子问题向原问题逐步求解。
使用条件:可分为多个相关子问题,子问题的解被重复使用

动态规划算法的设计步骤:
分析优化解的结构
递归地定义最优解的代价
自底向上地计算优化解的代价保存之,并获取构造最优解的信息
根据构造最优解的信息构造优化解

动态规划特点:
把原始问题划分成一系列子问题;
求解每个子问题仅一次,并将其结果保存在一个表中,以后用到时直接存取,不重复计算,节省计算时间
自底向上地计算。
整体问题最优解取决于子问题的最优解(状态转移方程)(将子问题称为状态,最终状态的求解归结为其他状态的求解)

动态规划与分治法的区别:
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。

1=例题Coin change

有银币面值2元,5元,7元无限,求最少的银币数量,刚好付清,如输入27,输出5(7+5+5+5+5)

(1)确定状态
最后一步:
K枚银币面值总和是27
一定有最后的一枚硬币:a
前面总面额是27-a
在这里插入图片描述
(我们不关心前面有多少种拼法)
(27-a的硬币数量一定要最少)(最优策略)
子问题
最少用多少枚硬币可以拼出27-a(规模更小)
如果a = 2, f(27) = f(27-2)+1
如果a = 5, f(27) = f(27-5)+1
如果a = 7, f(27) = f(27-7)+1
f(27) =min{f(25)+1,f(22)+1,f(20)+1}
(2)转移方程
f【27】 =min{f【25】+1,f【22】+1,f【20】+1}
(3)初始条件和边界情况
边界条件
Q1 x-2,x-5,x-7 小于0怎么办?
Q2 什么时候停下来?
Q3 拼不出来怎么办?
返回正无穷
初始条件 f[0]=0
(4)计算顺序;从小到大
算法复杂度O(n*m)

#include <stdio.h>
#include <math.h>
//Coin change
//有银币面值2元,5元,7元无限,求最少的银币,刚好付清,如输入27,输出5
#define max 10000
int min(int x,int y){
	if(x>y) return y;
	else return x;
}
int coinChange(int v[],int M){
		int f[M+1];
		f[0]=0;
		for(int i = 1;i<= M;i++){
			f[i] = max;
			for(int j = 0;j<3;j++){
				if(i>=v[j]&&f[i-v[j]]!=max){
					f[i]= min(f[i-v[j]]+1,f[i]);
				}
			}
		}
		if(f[M]==max){
			return -1;
		}
		return f[M];
}

int main(){
	int m;
	int v[3] = {2,5,7};
	scanf("%d",&m);
    printf("%d",coinChange(v,m));
	return 0;
} 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/87261
推荐阅读
相关标签
  

闽ICP备14008679号